41. Binary Tree Level Order Traversal

MediumTree Binary Tree BFS Queue

Given the root of a binary tree, return its node values level by level. The result is a list of levels from the root downwards, and each level lists its values from left to right.

An empty tree has no levels, so return an empty list.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1,2,null,3,null,4]
Output: [[1],[2],[3],[4]]

Explanation: A tree that only grows to the left has one node per level.

Example 3

Input: root = []
Output: []

Constraints

The number of nodes is in the range [0, 2000]
-1000 <= Node.val <= 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