DEV Community

Akhil
Akhil

Posted on

Binary Tree Level Order Traversal

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

Discussion (0)