educative.io

Educative

No queue solution

No real need for a queue for this problem

  class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}


const traverse = function (root) {
  let result = [];
  let level = [root]

  while (true) {
    const nextLevelNodes = []
    const values = []

    for (let i = 0; i < level.length; i++) {
      const node = level[i]
      const left = node.left
      const right = node.right

      // collect current level node values
      values.push(node.val)

      // collect next level nodes
      if (left) {
        nextLevelNodes.push(left)
      }

      if (right) {
        nextLevelNodes.push(right)
      }
    }

    result.push(values)

    // break if next level has no nodes
    if (nextLevelNodes.length === 0) {
      break
    }

    // set next level nodes
    level = nextLevelNodes
  }

  return result;
};



var root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(9);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);
console.log('Level order traversal:', traverse(root));

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Binary Tree Level Order Traversal (easy) - Grokking the Coding Interview: Patterns for Coding Questions

Hi @Nicolas_F,

Level order traversal in a binary search tree has multiple solutions using a queue, an array, or recursion. We can also implement the level order traversal with recursion but it increases the time complexity to O(N^2). With a queue/array, we can implement this in O(n) time complexity as implemented in the lesson.

We really appreciate your feedback. Feel free to post if you have any other queries.
Thanks.