Binary Tree Level Order Traversal

The problem

root is the top node of a binary tree, or null when the tree is empty. Each node has a number val and up to two children, left and right; a missing child is null. The root is on level 0, its children on level 1, their children on level 2, and so on. Return a list with one inner list per level, from level 0 down. Each inner list holds its level's values from left to right: a left child comes before a right child, and the children of an earlier node come before those of a later one. An empty tree returns an empty list.

What to write

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function solve(root: TreeNode | null): number[][]

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
[[1],[2,3]]

Input
root = null

Output
[]

Constraints

0–500 acyclic tree nodes.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 500 nodes, so speed is not the difficulty. The difficulty is the grouping: nodes on the same level can sit under different parents, far apart in the tree, and they still have to end up in one list, in order. The tree may also be empty; then the answer is an empty list.

2. Hint 2: Ask a smaller question

   Suppose you already hold all the nodes of one level, in order from left to right. How would you build the list of the nodes on the next level from them, also in order?

3. Hint 3: Name the pattern

   Reading a tree one whole level at a time, from the top down, is level-order tree traversal. Its tool is a queue, a line where you add at the back and take from the front: while you read one level from the front, its children line up at the back. The signal is an answer grouped by level. Read the lesson on level-order tree traversal.

4. Hint 4: State the invariant

   At the start of every round, the queue holds exactly the nodes of one level, from left to right, and nothing else. Reading that many nodes, and adding their children as you go, leaves exactly the next level in the queue.

5. Hint 5: Sketch the pseudocode

   If the root is missing, return an empty list. Put the root in a queue. While the queue has nodes: count them and start a level list. That many times: take the front node, append its value to the level list, and add its existing children to the back, left first. Append the level list to the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Maintain a queue and freeze its current end at each level. Process only those nodes before starting the next level’s output.

The slow way

First find how many levels the tree has. Then, for each level number in turn, walk the tree again from the root and collect the nodes on that level. It is correct, but every level starts over from the top. A tree that is one long chain of n nodes costs about n × n / 2 visits.

The insight

The children of one level's nodes, taken in the same order, are exactly the next level. So if you hold a whole level, one pass over it gives you its values and the complete next level. A queue keeps the two apart: you read from the front while the children wait at the back.

Step by step

1. An empty tree has no levels. With no root there is nothing to read, so the answer is an empty list. After this check the queue only ever holds real nodes.
2. Start a queue that holds only the root. A queue gives nodes back in the order they were added. The root alone is all of level 0, so the queue starts out holding one complete level.
3. Everything waiting in the queue now is one level: mark where it ends. Children join the same queue while the level is being read. Deciding beforehand where the level ends keeps them out of it.
4. Take the node at the front and record its value. The front node is the leftmost one of this level that has not been read, so the values land in the level's list from left to right.
5. Add its children at the back, left child first. They belong to the next level, so they wait behind everything still to be read. Left before right keeps the next level in order too.
6. The level is complete: add it to the answer. Exactly the nodes that were waiting at the start have been read. The list holds one whole level, and what is now in the queue is the next one.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. An empty tree has no levels
  if (!root) return [];
  // 2. Start a queue that holds only the root
  const out = [],
    q = [root];
  // Removing the first item of an array is slow, so nothing is removed:
  // h is the position of the front, and the nodes before it have been read.
  let h = 0;
  // 3. Everything waiting in the queue now is one level: mark where it ends
  while (h < q.length) {
    const end = q.length,
      level = [];
    while (h < end) {
      // 4. Take the node at the front and record its value
      const node = q[h++];
      level.push(node.val);
      // 5. Add its children at the back, left child first
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    // 6. The level is complete: add it to the answer
    out.push(level);
  }
  return out;
}

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function solve(root: TreeNode | null): number[][] {
  // 1. An empty tree has no levels
  if (!root) return [];
  // 2. Start a queue that holds only the root
  const out = [],
    q = [root];
  // Removing the first item of an array is slow, so nothing is removed:
  // h is the position of the front, and the nodes before it have been read.
  let h = 0;
  // 3. Everything waiting in the queue now is one level: mark where it ends
  while (h < q.length) {
    const end = q.length,
      level = [];
    while (h < end) {
      // 4. Take the node at the front and record its value
      const node = q[h++];
      level.push(node.val);
      // 5. Add its children at the back, left child first
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    // 6. The level is complete: add it to the answer
    out.push(level);
  }
  return out;
}

from collections import deque


def solve(root):
    # 1. An empty tree has no levels
    if root is None:
        return []
    # 2. Start a queue that holds only the root
    out = []
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque([root])
    # 3. Everything waiting in the queue now is one level: mark where it ends
    while queue:
        level = []
        # len(queue) is read once, here, before any child joins the queue.
        for _ in range(len(queue)):
            # 4. Take the node at the front and record its value
            node = queue.popleft()
            level.append(node.val)
            # 5. Add its children at the back, left child first
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # 6. The level is complete: add it to the answer
        out.append(level)
    return out

Example 1, traced

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
[[1],[2,3]]

Why it works

At the start of each round the queue holds exactly one level, in order. Reading those nodes adds all their children at the back, in the same order, and that is exactly the next level. The root starts the chain as level 0, so every level is listed once, from the top down.

Time and space

Time O(n), extra space O(n). Every node is added to the queue once and read from it once, with a fixed amount of work each time, so the time is O(n). The answer holds all n values and the queue never holds more than n nodes, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Mark where the level ends before you read any of it. If the inner loop runs until the queue is empty, children are read in their parents' level, and example 1 comes out as [[1, 2, 3]].
• Add the left child before the right child. The other order turns every level around: example 1 gives [[1], [3, 2]].
• Never put a missing node in the queue. Check that the root exists, and check each child before adding it. Reading the value of a missing node stops the program with an error.

Pattern

Level-order tree traversal.

Keep going