DEV Community

Akhil
Akhil

Posted on

Binary Tree Level Order Traversal

#javascript #algorithms #interview #computerscience

Question: give a tree, return the level order traversal of the tree.

so for given tree:

Alt Text

output would be :

[ [10], [5 ,7 ], [15, 9, 20] ]
Enter fullscreen mode Exit fullscreen mode

So what is meant by level order traversal?

Alt Text

If you observe closely, it's a Breadth-first traversal algorithm.

So question boils down to how to Breadth-first traverse a tree.

Read more about it : https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/

So for this question solution is :

var levelOrder = function(root) { if (!root) return []; const res = []; const q = []; q.push(root); while(q.length) { const lvl = []; const size = q.length; for (let i = 0; i < size; i++) { const node = q.shift(); lvl.push(node.val); if (node.left) q.push(node.left); if (node.right) q.push(node.right); } res.push(lvl); } return res; };
Enter fullscreen mode Exit fullscreen mode

github:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/breadthFirstSearch.js

Top comments (0)