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:

output would be :

[ [10],
  [5 ,7 ],
  [15, 9, 20]
]

So what is meant by level order traversal?

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

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

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;
};