Trees · pattern 3 of 8

Level-order tree traversal

Read a tree one whole level at a time, from the top down. The nodes wait in a queue, a line where you add at the back and take from the front. While one level is read, its children line up behind it.

Watch it run in the app

When to use it

Use it when the answer is grouped by level, or is about each level, or is the node nearest to the root, the top node.

It belongs to the trees group: Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

Watch it work

A company chart is a tree with the boss on level 0, the people who report to the boss on level 1, and so on. Each person has a bonus. Return the level whose bonuses add up to the most.

Input
root = [7, 9, 4, 2, null, 3, 1]

Output
1

root reaches the code as a tree, written here level by level: each node has a value, val, and two children, left and right.

The method

Start a queue that holds the root, if there is one
All that waits now is one level: mark where it ends
Take the front node and add its value to the total
Add its children at the back, left child first
The level is complete: keep it if its total is the largest
The queue is empty: return the best level

The run, one moment at a time

Step 1. The root, 7, goes into the queue. No level has been read yet.
```
queue: 7
level: 0
total: 0
largest: empty
best level: empty
```
Step 2. The queue holds one node, 7. All that waits now is level 0, so the level ends after 7.
```
queue: 7  (end at 0)
level: 0
total: 0
largest: empty
best level: empty
```
Step 4. Node 7 has been taken from the front: the total of level 0 is 7. Now its children, 9 and 4, join the back. Level 0 has no node left, so all that waits is level 1.
```
queue: 9 4
level: 0
total: 7
largest: empty
best level: empty
```
Step 5. Level 0 is complete. Its total, 7, is the largest so far, so the best level is 0.
```
queue: 9 4
level: 0
total: 7
largest: 7
best level: 0
```
Step 2. The queue holds 9 and 4 and nothing else: that is all of level 1, from left to right. The level ends after 4.
```
queue: 9 4  (end at 1)
level: 1
total: 0
largest: 7
best level: 0
```
Step 4. Node 9 has been taken from the front: the total of level 1 is 9. Now its only child, 2, joins the back, behind 4, where level 1 ends. It waits for the next level.
```
queue: 4 2  (end at 0)
level: 1
total: 9
largest: 7
best level: 0
```
Step 4. Node 4 has been taken from the front: the total is 9 + 4 = 13. Now its children, 3 and 1, join the back. Level 1 has no node left, so all that waits is level 2.
```
queue: 2 3 1
level: 1
total: 13
largest: 7
best level: 0
```
Step 5. Level 1 is complete. Its total, 13, is larger than 7, so the best level is now 1.
```
queue: 2 3 1
level: 1
total: 13
largest: 13
best level: 1
```
Step 2. The queue holds 2, 3 and 1 and nothing else: that is all of level 2, from left to right. The level ends after 1.
```
queue: 2 3 1  (end at 2)
level: 2
total: 0
largest: 13
best level: 1
```
Step 3. Take 2, 3 and 1 from the front, one at a time: 2 + 3 + 1 = 6. None of them has children, so nothing joins the queue.
```
queue: empty
level: 2
total: 6
largest: 13
best level: 1
```
Step 5. Level 2 is complete. Its total, 6, is not larger than 13, so the best level stays 1.
```
queue: empty
level: 2
total: 6
largest: 13
best level: 1
```
Step 6. The queue is empty, so every level has been read. Level 1 has the largest total, 13: the answer is 1.
```
queue: empty
largest: 13
best level: 1
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(root) {
  // 1. Start a queue that holds the root, if there is one
  const queue = [];
  if (root) queue.push(root);
  // Taking from the front of an array is slow, so nothing is removed:
  // head is the position of the front.
  let head = 0;
  let level = 0;
  let best = -1;
  let largest = -Infinity;
  while (head < queue.length) {
    // 2. All that waits now is one level: mark where it ends
    const end = queue.length;
    let total = 0;
    while (head < end) {
      // 3. Take the front node and add its value to the total
      const node = queue[head];
      head++;
      total += node.val;
      // 4. Add its children at the back, left child first
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    // 5. The level is complete: keep it if its total is the largest
    if (total > largest) {
      largest = total;
      best = level;
    }
    level++;
  }
  // 6. The queue is empty: return the best level
  return best;
}

Python

from collections import deque

def solve(root):
    # 1. Start a queue that holds the root, if there is one
    # A deque is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque()
    if root:
        queue.append(root)
    level = 0
    best = -1
    largest = float("-inf")
    while queue:
        # 2. All that waits now is one level: mark where it ends
        size = len(queue)
        total = 0
        for _ in range(size):
            # 3. Take the front node and add its value to the total
            node = queue.popleft()
            total += node.val
            # 4. Add its children at the back, left child first
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # 5. The level is complete: keep it if its total is the largest
        if total > largest:
            largest = total
            best = level
        level += 1
    # 6. The queue is empty: return the best level
    return best

How to spot it

Given: The root is on level 0, its children on level 1: A problem that numbers the levels usually wants an answer for each level, which is what this walk produces.
Asked: Return the values level by level, from the top down: The queue hands the nodes over in exactly that order: all of one level before any node of the next.
Asked: The largest, the total or the average value of each level: Each of these needs all the nodes of one level together. The size of the queue when a level starts says where that level ends.
Asked: The fewest steps down from the root to reach something: Levels are read in order of distance from the root, so the first match met is the nearest and the walk can stop.

Looks like it, but is not

A node's answer needs everything below it, such as its height or the total under it. Use Postorder tree recursion. A level says nothing about what is below a node. The children must answer first and hand the result up.
Each node needs to know its level, but nodes of one level need not be handled together. Use Preorder tree recursion. A parent can pass the level down as a number. That is less code than a queue when levels need not stay together.
The nearest thing is asked for in a grid or a network, not in a tree. Use Breadth-first search by distance. The same queue is used, but a grid or a network can lead back to a place already seen, so seen places must be remembered.

Cost and mistakes

Time grows with the number of nodes, written O(n): each node joins the queue once and leaves it once. Extra space is the queue, also O(n): a whole level waits in it, and the widest level of a full tree is about half the nodes.

Watch out

Read the size of the queue once, before the level starts. If you test the length of the queue while children are joining it, the next level is read as part of this one.
Never put a missing child in the queue. Check that each child exists before you add it, and check the root too, or the code later reads the value of nothing.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.

Show it

Binary Tree Level Order TraversalMedium · Trees