Binary Tree Level Order Traversal

MediumTree Binary Tree BFS Queue

A phone tree spreads urgent news through a team: the organizer calls up to two people, each of them calls up to two more, and so on. The tree is stored as a binary tree, and everyone at the same depth hears the news in the same round of calls.

Given the root, return the node values grouped by round: a list of levels from the root downwards, where each level lists its values from left to right. An empty tree has no rounds, so return an empty list.

Example 1

Input: root = [5,1,8,null,4,7,9]
Output: [[5],[1,8],[4,7,9]]

Explanation: The organizer 5 calls 1 and 8. In the third round, 1 calls 4 while 8 calls 7 and 9.

Example 2

Input: root = [2,null,6,3]
Output: [[2],[6],[3]]

Explanation: Each round reaches a single person.

Example 3

Input: root = [7,3,null,1,5]
Output: [[7],[3],[1,5]]

Constraints

The tree has at most 2000 nodes.
Node values are integers from -1000 to 1000.

💡 Hint 1

Nodes should come out in the order they are discovered, level after level. Which structure hands items back first-in, first-out?

💡 Hint 2

Before draining the queue for a level, record its current size. Exactly that many nodes belong to the level; their children form the next one.

💡 Hint 3

A DFS works too if you pass the depth along and append each value to result[depth].

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Breadth-first search with a queue. Start with the root in the queue. On each round, note how many nodes the queue holds: that is the whole current level. Dequeue exactly that many, record their values in order, and enqueue their non-null children, which together make up the next level. Stop when the queue is empty.

Time O(n)Space O(w), where w is the widest level (up to n/2)

function levelOrder(root) {
  const result = [];
  let level = root ? [root] : [];
  while (level.length) {
    result.push(level.map((node) => node.val));
    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;
  }
  return result;
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {number[][]}
 */
function levelOrder(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit