Commitc4ace61

authored

Merge pull requestmgechev#118 from shaunak1111/Level_Order_traversal_Red_Black_Tree

Level Order Traversal for red black tree using queue.

2 parents8369dca +40b0658 commitc4ace61Copy full SHA for c4ace61

File tree

+46

-0

lines changed

+46

-0

lines changed

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -266,4 +266,34 @@`
`266`	`266`	`}`
`267`	`267`	`};`
`268`	`268`
	`269`	`+/**`
	`270`	`+ * Get Level Order Traversal for the given Red Black Tree,`
	`271`	`+ * returns 'Tree is empty' string when tree has no Nodes.`
	`272`	`+ * Complexity: O(N).`
	`273`	`+ *`
	`274`	`+ *@public`
	`275`	`+ *@return {String} The keys of the tree in level order traversal.`
	`276`	`+ *`
	`277`	`+ */`
	`278`	`+exports.RBTree.prototype.levelOrderTraversal=function(){`
	`279`	`+varqueue=[];`
	`280`	`+varlevelOrderString='';`
	`281`	`+if(this._root){`
	`282`	`+queue.push(this._root);`
	`283`	`+}else{`
	`284`	`+levelOrderString=' Tree is empty';`
	`285`	`+}`
	`286`	`+while(queue.length!==0){`
	`287`	`+vartempNode=queue.shift();`
	`288`	`+levelOrderString+=' '+tempNode.getKey();`
	`289`	`+if(tempNode.getLeft()!==null){`
	`290`	`+queue.push(tempNode.getLeft());`
	`291`	`+}`
	`292`	`+if(tempNode.getRight()!==null){`
	`293`	`+queue.push(tempNode.getRight());`
	`294`	`+}`
	`295`	`+}`
	`296`	`+return'Level Order Traversal -:'+levelOrderString;`
	`297`	`+};`
	`298`	`+`
`269`	`299`	`})(typeofwindow==='undefined' ?module.exports :window);`

Lines changed: 16 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -97,4 +97,20 @@ describe('RBTree', function () {`
`97`	`97`	`});`
`98`	`98`	`});`
`99`	`99`
	`100`	`+describe('levelOrderTraversal method',function(){`
	`101`	`+it('should be able to traverse tree in level order',function(){`
	`102`	`+vartree=newRBTree();`
	`103`	`+expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: Tree is empty');`
	`104`	`+tree.put(10);`
	`105`	`+tree.put(20);`
	`106`	`+expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10');`
	`107`	`+tree.put(30);`
	`108`	`+expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 30');`
	`109`	`+tree.put(45);`
	`110`	`+expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 45 30');`
	`111`	`+tree.put(5);`
	`112`	`+expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 45 5 30');`
	`113`	`+});`
	`114`	`+});`
	`115`	`+`
`100`	`116`	`});`

Comments

(0)