Level-order traversal template

Level-order traversal visits a tree one level at a time: the root first, then every node one step below it, then every node two steps below, each level from left to right. It is breadth-first search on a tree, and a queue produces exactly that order, because nodes leave a queue in the order they joined it. The template adds one step that many interview problems need: when a level starts, read how many nodes the queue holds and take exactly that many. Those nodes are the whole level, so you can list them, count them, add them up, average them or keep the largest, and record one answer per level. Each node joins and leaves the queue once, so the walk takes O(n) time for n nodes, and the queue never holds more than the current level and the next one. This lesson builds the template in Python and traces it, shows the slip that makes JavaScript versions mix up their levels, runs the same loop on an org chart where a person can have any number of reports, and measures what the choice of queue costs on a tree of 100,000 nodes.

Why a queue visits a tree level by level

Put the root in a queue. Then repeat: take the node at the front, and add its children at the back, left child first. A child always joins behind everything that is already waiting, and everything waiting is either on its parent’s level or on the level just below. So every node of one level leaves the queue before any node of the next level, and children leave in the order their parents did, which is left to right.

Each row of the diagram is what the queue holds at the moment that level starts. That is the template’s invariant: when a level starts, the queue holds every node of that level, in order, and nothing else.

• True at the start. The queue contains only the root, which is the whole of level 0.
• Each level keeps it true. While a level runs, its nodes leave from the front and their children join at the back. When the level’s last node has left, the queue holds exactly their children: the next level, left to right.
• It ends the walk. An empty queue means there is no next level.

The invariant is what makes the level-size loop work: if the queue holds exactly one level when the level starts, its length is the number of nodes in that level. Unlike breadth-first search on a graph, the walk needs no set of visited nodes. Every node except the root has exactly one parent, and only that parent ever adds it to the queue.

The template: a queue and a level-size loop

The examples use the tree of the diagram. tree.py holds a three-field Node class and build, which reads a tree written as a list in level order, with None where a child is missing: a compact way to write trees for tests. build is itself a level-order walk, because each node it takes from its queue claims the next two values of the list as its children.

from collections import deque

from tree import build


def level_order(root):
    """The values of the tree, one list per level, each level from left to right."""
    levels = []
    if root is None:
        return levels
    queue = deque([root])
    while queue:
        values = []
        for _ in range(len(queue)):  # len(queue) is read once: exactly the nodes of this level
            node = queue.popleft()
            values.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(values)
    return levels


print(level_order(build([8, 4, 11, 2, 6, None, 14, None, None, 5])))
print(level_order(build([7])))
print(level_order(build([1, None, 2, None, 3])))
print(level_order(None))

[[8], [4, 11], [2, 6, 14], [5]]
[[7]]
[[1], [2], [3]]
[]

"""A binary tree node, and a builder that reads a tree written as a list in level order."""
from collections import deque


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build(values):
    """Builds a tree from its values in level order, with None where a child is missing.

    [8, 4, 11, 2, 6, None, 14] is the root 8 with children 4 and 11; 4 has the children 2 and 6, and 11 has no left
    child and 14 on its right. Each node taken from the queue claims the next two values as its children, so the
    builder is itself a level-order walk.
    """
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root

Four details make it work:

1. An empty tree has no levels. The check comes first, so None never enters the queue.
2. deque([root]) starts the queue with level 0. A collections.deque removes items from the front in constant time; the section on choosing the queue explains why a list would not.
3. for _ in range(len(queue)) takes exactly one level. Python’s language reference says that the expression list of a for statement is evaluated once, so the range is built from the length the queue had when the level started. Children appended while the loop runs wait for the next level.
4. Children join at the back, left first, and only if they exist.

The other three calls cover edge cases: a single node is one level, a chain that only goes right, [1, None, 2, None, 3], has one node on each of its three levels, and an empty tree has no levels at all. Each node is appended once and removed once, so the time is O(n), and the memory beyond the output is the queue.

A dry run of the queue

Trace the queue on a small tree before you trust the code. This version prints it after every step:

"""The level-order template on the sample tree, printing the queue after every step."""
from collections import deque

from tree import build


def show(queue):
    return "[" + ", ".join(str(node.val) for node in queue) + "]"


root = build([8, 4, 11, 2, 6, None, 14, None, None, 5])
queue = deque([root])
level = 0
while queue:
    size = len(queue)
    print(f"level {level}: the queue holds {show(queue)}, so take {size}")
    for _ in range(size):
        node = queue.popleft()
        children = [child for child in (node.left, node.right) if child is not None]
        queue.extend(children)
        added = " and ".join(str(child.val) for child in children) or "nothing"
        print(f"  take {node.val}, add {added}".ljust(24) + f"queue {show(queue)}")
    level += 1
print(f"the queue is empty after {level} levels")

level 0: the queue holds [8], so take 1
  take 8, add 4 and 11  queue [4, 11]
level 1: the queue holds [4, 11], so take 2
  take 4, add 2 and 6   queue [11, 2, 6]
  take 11, add 14       queue [2, 6, 14]
level 2: the queue holds [2, 6, 14], so take 3
  take 2, add nothing   queue [6, 14]
  take 6, add 5         queue [14, 5]
  take 14, add nothing  queue [5]
level 3: the queue holds [5], so take 1
  take 5, add nothing   queue []
the queue is empty after 4 levels

Look at the line where level 2 starts. The two lines above it show how the queue got there: taking 4 added 2 and 6 behind 11, and taking 11 added 14, so when level 1’s last node had left, exactly level 2 remained. Every level starts that way, which is the invariant at work. The lesson on dry runs and invariants shows how to keep a trace table like this one by hand.

A common slip: a level bound that keeps moving

In JavaScript it is easy to write the level loop with queue.length in its condition. The ECMAScript specification evaluates the test of a for loop again before every iteration, and this queue grows and shrinks while the level runs:

// A level loop whose bound is read again before every iteration: the levels come out wrong.
function node(val, left = null, right = null) {
  return { val, left, right };
}

function levelsWrong(root) {
  const levels = [];
  const queue = [root];
  while (queue.length > 0) {
    const values = [];
    for (let i = 0; i < queue.length; i++) { // queue.length changes while this level is taken
      const current = queue.shift();
      values.push(current.val);
      if (current.left !== null) queue.push(current.left);
      if (current.right !== null) queue.push(current.right);
    }
    levels.push(values);
  }
  return levels;
}

const sample = node(8, node(4, node(2), node(6, node(5))), node(11, null, node(14)));
console.log(JSON.stringify(levelsWrong(sample)));

[[8,4,11],[2,6],[14],[5]]

The output still looks like a list of levels, which is why the slip survives a glance. Level 0 should hold 8 alone, but when i reaches 1 the queue already holds 4 and 11, so the loop goes on and takes them too. Every later level starts in the wrong place as well. The fix is the one Python’s range applies by itself: read the length into a variable before the level starts. The version below does that, and it also keeps the front of the queue as an index, head, instead of calling shift(), for reasons the next section measures.

// The level-order template in JavaScript: an array and a head index instead of shift().
function node(val, left = null, right = null) {
  return { val, left, right };
}

function levelOrder(root) {
  const levels = [];
  if (root === null) return levels;
  const queue = [root];
  let head = 0; // queue[head] is the next node to take; nothing is ever removed
  while (head < queue.length) {
    const end = queue.length; // read once: this level is queue[head] to queue[end - 1]
    const values = [];
    while (head < end) {
      const current = queue[head++];
      values.push(current.val);
      if (current.left !== null) queue.push(current.left);
      if (current.right !== null) queue.push(current.right);
    }
    levels.push(values);
  }
  return levels;
}

const sample = node(8, node(4, node(2), node(6, node(5))), node(11, null, node(14)));
console.log(JSON.stringify(levelOrder(sample)));
console.log(JSON.stringify(levelOrder(node(7))));
console.log(JSON.stringify(levelOrder(null)));

[[8],[4,11],[2,6,14],[5]]
[[7]]
[]

const end = queue.length is read once per level. The nodes from head to end - 1 are the level; children pushed while it runs land at end and beyond, so they wait for the next level, as they do in Python.

Choosing the queue in each language

The template takes a node from the front of its queue n times, so the cost of that one operation decides whether the whole walk is O(n) or O(n²).

• Python: collections.deque. Python’s documentation promises roughly constant time for adding or removing items at either end of a deque, and warns that pop(0) on a list costs O(n), since every later item has to shift. The table of time complexities lists l.pop(k) as O(n − k), which is the whole list when k is 0.
• JavaScript: an array and a head index, as above, or a new array for each level. The standard library has no deque, and the specification defines shift() as a loop that moves every remaining element down one place.
• Java: ArrayDeque, with offer and poll. The Java documentation expects it to beat LinkedList as a queue, and it rejects null outright: offer(null) throws a NullPointerException, so test each child before adding it. LinkedList accepts null, so on a linked list the same slip adds a null that fails later, when the loop reads its value.
• C++: std::queue. The standard defines it on top of a std::deque unless you name another container. Its pop() returns nothing, so read front() first, and test child pointers against nullptr before pushing them.

What shift() costs on 100,000 nodes

This program computes the level sums of a complete binary tree of 100,000 nodes with shift() and with a head index, three times each, and keeps the fastest time of each. It also counts the items that shift() has to move, by the specification’s description of it:

// Level sums of a complete binary tree of 100,000 nodes, computed twice: with shift() and with a head index.
const N = 100_000;

function completeTree(n) {
  // Node i has the children 2i + 1 and 2i + 2, the layout of a binary heap.
  const nodes = Array.from({ length: n }, (_, i) => ({ val: i % 1000, left: null, right: null }));
  for (let i = 0; i < n; i++) {
    if (2 * i + 1 < n) nodes[i].left = nodes[2 * i + 1];
    if (2 * i + 2 < n) nodes[i].right = nodes[2 * i + 2];
  }
  return nodes[0];
}

function sumsWithShift(root) {
  const sums = [];
  const queue = [root];
  let moved = 0;
  while (queue.length > 0) {
    const size = queue.length;
    let sum = 0;
    for (let i = 0; i < size; i++) {
      moved += queue.length - 1; // shift() moves every item behind the first one down one place
      const current = queue.shift();
      sum += current.val;
      if (current.left !== null) queue.push(current.left);
      if (current.right !== null) queue.push(current.right);
    }
    sums.push(sum);
  }
  return { sums, moved };
}

function sumsWithHead(root) {
  const sums = [];
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const end = queue.length;
    let sum = 0;
    while (head < end) {
      const current = queue[head++];
      sum += current.val;
      if (current.left !== null) queue.push(current.left);
      if (current.right !== null) queue.push(current.right);
    }
    sums.push(sum);
  }
  return { sums, moved: 0 };
}

const root = completeTree(N);
const results = [];
for (const run of [sumsWithShift, sumsWithHead]) {
  // The fastest of three runs, so that a busy moment of the computer counts for less.
  let fastest = Infinity;
  let result;
  for (let k = 0; k < 3; k++) {
    const start = performance.now();
    result = run(root);
    fastest = Math.min(fastest, performance.now() - start);
  }
  results.push({ ...result, ms: fastest });
  console.log(`${run.name}: ${result.sums.length} levels, ${result.moved.toLocaleString('en-US')} items moved, ${Math.round(fastest)} ms`);
}
const same = JSON.stringify(results[0].sums) === JSON.stringify(results[1].sums);
const times = Math.round(results[0].ms / Math.max(results[1].ms, 0.1));
console.log(`same level sums: ${same}; shift() took ${times} times as long`);

sumsWithShift: 17 levels, 2,499,950,000 items moved, 1542 ms
sumsWithHead: 17 levels, 0 items moved, 2 ms
same level sums: true; shift() took 644 times as long

Both versions find the same 17 level sums. The count does not depend on the computer: in a tree of this shape the queue holds about 25,000 nodes on average, and each of the 100,000 calls of shift() moves all but one of them, 2,499,950,000 moves in all. The times do depend on the computer, and an engine may find shortcuts that the specification’s step-by-step description does not show, but the last line of the output shows how little that helped on this run. A head index costs memory instead, because the array keeps every node it has ever held. For 10⁵ nodes that is harmless; when it is not, build a new array for each level, as the two-lists way below does.

The template in Java and C++

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    static final class Node {
        final int val;
        final Node left;
        final Node right;

        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        Node(int val) {
            this(val, null, null);
        }
    }

    static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(); // read once, before the level starts
            List<Integer> values = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                values.add(node.val);
                if (node.left != null) queue.offer(node.left); // ArrayDeque refuses null
                if (node.right != null) queue.offer(node.right);
            }
            levels.add(values);
        }
        return levels;
    }

    public static void main(String[] args) {
        Node sample = new Node(8,
                new Node(4, new Node(2), new Node(6, new Node(5), null)),
                new Node(11, null, new Node(14)));
        System.out.println(levelOrder(sample));
        System.out.println(levelOrder(null));
        try {
            new ArrayDeque<Node>().offer(sample.right.left);
        } catch (NullPointerException e) {
            System.out.println("offer(null) on an ArrayDeque: NullPointerException");
        }
    }
}

#include <cstddef>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

struct Node {
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
};

std::vector<std::vector<int>> level_order(Node* root) {
    std::vector<std::vector<int>> levels;
    if (root == nullptr) return levels;
    std::queue<Node*> queue;  // a std::deque underneath
    queue.push(root);
    while (!queue.empty()) {
        const std::size_t size = queue.size();  // read once, before the level starts
        std::vector<int> values;
        for (std::size_t i = 0; i < size; ++i) {
            Node* node = queue.front();  // pop() returns nothing, so read the front first
            queue.pop();
            values.push_back(node->val);
            if (node->left != nullptr) queue.push(node->left);
            if (node->right != nullptr) queue.push(node->right);
        }
        levels.push_back(std::move(values));
    }
    return levels;
}

void print(const std::vector<std::vector<int>>& levels) {
    std::cout << '[';
    for (std::size_t i = 0; i < levels.size(); ++i) {
        std::cout << (i ? ", [" : "[");
        for (std::size_t j = 0; j < levels[i].size(); ++j) std::cout << (j ? ", " : "") << levels[i][j];
        std::cout << ']';
    }
    std::cout << "]\n";
}

int main() {
    Node five{5}, two{2}, fourteen{14};
    Node six{6, &five, nullptr};
    Node four{4, &two, &six};
    Node eleven{11, nullptr, &fourteen};
    Node root{8, &four, &eleven};
    print(level_order(&root));
    print(level_order(nullptr));
}

"""Runs the Java and C++ versions of the template the way you would in a terminal, and prints the session.

Each command is shown after "$ ", followed by what it printed (standard output and standard error together, as a
terminal shows them) and, if it failed, its exit status. The first lines name the compilers, without their release
dates. On this Mac, `java` is Homebrew's OpenJDK and `clang++` is the compiler of Apple's Command Line Tools, called
directly with SDKROOT naming the SDK whose headers it compiles against.
"""
import os
import re
import subprocess

JDK_FOLDERS = ["/opt/homebrew/opt/openjdk/bin", "/usr/local/opt/openjdk/bin"]
CLANG_FOLDER = "/Library/Developer/CommandLineTools/usr/bin"
SDK = "/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk"
RELEASE_DATE = re.compile(r"\s+\d{4}-\d{2}-\d{2}")

env = dict(os.environ)
env["PATH"] = os.pathsep.join([*JDK_FOLDERS, CLANG_FOLDER, env.get("PATH", "")])
env["SDKROOT"] = SDK


def run(command):
    return subprocess.run(command, shell=True, env=env, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)


for command in ("java -version", "clang++ --version"):
    lines = run(command).stdout.splitlines()
    print("#", RELEASE_DATE.sub("", lines[0]) if lines else f"{command}: not found")

for command in (
    "java LevelOrder.java",
    "clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined level_order.cpp -o level_order",
    "./level_order",
):
    print(f"$ {command}")
    result = run(command)
    print(result.stdout, end="")
    if result.returncode != 0:
        print(f"[exit status {result.returncode}]")
        break

# openjdk version "27"
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java LevelOrder.java
[[8], [4, 11], [2, 6, 14], [5]]
[]
offer(null) on an ArrayDeque: NullPointerException
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined level_order.cpp -o level_order
$ ./level_order
[[8], [4, 11], [2, 6, 14], [5]]
[]

Both print the sample’s levels as the Python version does. The java launcher can run a single source file directly, so java LevelOrder.java needs no separate javac step. The program’s last line shows ArrayDeque refusing a null child: 11 has no left child, and offering that missing child throws. The C++ command turns on compiler warnings and two run-time checkers, AddressSanitizer for bad memory reads and writes and UndefinedBehaviorSanitizer for operations such as signed overflow, and the run printed no complaint from either.

Per-level answers on an N-ary tree: an org chart

The template returns lists of values, but its inner loop can fold a level into any summary: start the summary when the level starts, update it for each node taken, and record it when the level ends. An org chart shows that, and it is also an N-ary tree, where a node can have any number of children. Here each person has a yearly salary in thousands and a list of direct reports:

"""Headcount, payroll and average salary on each level of an org chart, where a person has any number of reports."""
from collections import deque


class Person:
    def __init__(self, name, salary, reports=()):
        self.name = name
        self.salary = salary  # a year, in thousands
        self.reports = list(reports)  # direct reports, in the order the chart lists them


def pay_by_level(top):
    """(people, total, average) for each level of the chart, from the top down."""
    rows = []
    queue = deque([top])
    while queue:
        size = len(queue)
        total = 0
        for _ in range(size):
            person = queue.popleft()
            total += person.salary
            queue.extend(person.reports)  # every child, in order: the only change for an N-ary tree
        rows.append((size, total, total / size))
    return rows


chart = Person("Asha", 400, [
    Person("Bilal", 220, [Person("Chen", 150), Person("Dara", 140), Person("Eitan", 135)]),
    Person("Farida", 210, [Person("Gopal", 120, [Person("Hana", 70), Person("Ivo", 65)])]),
    Person("Jonas", 180, [Person("Kiri", 110), Person("Lena", 105, [Person("Malik", 60)])]),
])

print("level  people  total  average")
for level, (people, total, average) in enumerate(pay_by_level(chart)):
    print(f"{level:>5}  {people:>6}  {total:>5}  {average:>7.2f}")

level  people  total  average
    0       1    400   400.00
    1       3    610   203.33
    2       6    760   126.67
    3       3    195    65.00

Three details matter.

• One line changes for an N-ary tree. queue.extend(person.reports) adds every report, in the chart’s order, where the binary template had two if tests. A person with no reports adds nothing, so leaves need no special case.
• The level’s size is read before the loop. It is the headcount, and it is the divisor of the average.
• total / size is true division in Python, so the second level’s average is 203.33 rather than 203. The value is rounded to two decimals only when it is printed.

The rows answer the questions a people team might ask: average pay falls from 400 at the top to 65 three levels down, and level 2, with 6 people, is the widest. Other one-number summaries fit the same slot: a count, the largest or the smallest value, the first or the last node of the level, or whether any node of the level meets a condition.

Other ways to tell where a level ends

The level-size loop is one of four common ways to know when a level ends. This program checks all four on 1,000 random trees against the definition of level order itself: sort the nodes by depth, then by their path from the root read as a binary number, with 0 for a step to the left and 1 for a step to the right.

"""Four ways to tell where one level ends and the next begins, each checked on 1,000 random trees."""
import random
from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def children(node):
    return [child for child in (node.left, node.right) if child is not None]


def by_definition(root):
    """Level order from its definition: nodes sorted by depth, then by their path from the root read in binary."""
    found = []
    stack = [(root, 0, 0)] if root else []
    while stack:
        node, depth, path = stack.pop()
        found.append((depth, path, node.val))
        if node.left is not None:
            stack.append((node.left, depth + 1, 2 * path))
        if node.right is not None:
            stack.append((node.right, depth + 1, 2 * path + 1))
    levels = []
    for depth, _, val in sorted(found):
        if depth == len(levels):
            levels.append([])
        levels[depth].append(val)
    return levels


def level_size_loop(root):
    """The template: read the queue's length before each level."""
    levels = []
    queue = deque([root] if root else [])
    while queue:
        values = []
        for _ in range(len(queue)):
            node = queue.popleft()
            values.append(node.val)
            queue.extend(children(node))
        levels.append(values)
    return levels


def two_lists(root):
    """Build the next level as a new list from the current one."""
    levels = []
    level = [root] if root else []
    while level:
        levels.append([node.val for node in level])
        level = [child for node in level for child in children(node)]
    return levels


def depth_pairs(root):
    """Queue (node, depth) pairs; a depth seen for the first time starts a new level."""
    levels = []
    queue = deque([(root, 0)] if root else [])
    while queue:
        node, depth = queue.popleft()
        if depth == len(levels):
            levels.append([])
        levels[depth].append(node.val)
        queue.extend((child, depth + 1) for child in children(node))
    return levels


def recursion(root, right_first=False):
    """Depth-first, passing the depth down to each call."""
    levels = []

    def visit(node, depth):
        if depth == len(levels):
            levels.append([])
        levels[depth].append(node.val)
        for child in reversed(children(node)) if right_first else children(node):
            visit(child, depth + 1)

    if root:
        visit(root, 0)
    return levels


def random_tree(rng, size):
    """A random binary tree of `size` nodes valued 0 to size - 1: each new node takes a random empty child slot."""
    if size == 0:
        return None
    root = Node(0)
    slots = [(root, "left"), (root, "right")]
    for val in range(1, size):
        parent, side = slots.pop(rng.randrange(len(slots)))
        child = Node(val)
        setattr(parent, side, child)
        slots += [(child, "left"), (child, "right")]
    return root


rng = random.Random(12)
trees = [random_tree(rng, rng.randint(0, 40)) for _ in range(1000)]
expected = [by_definition(tree) for tree in trees]
ways = [
    ("level-size loop", level_size_loop),
    ("two lists", two_lists),
    ("(node, depth) pairs", depth_pairs),
    ("recursion, left first", recursion),
    ("recursion, right first", lambda root: recursion(root, right_first=True)),
]
for name, way in ways:
    matches = sum(way(tree) == want for tree, want in zip(trees, expected))
    print(f"{name:<23} matches on {matches:>4} of {len(trees)} trees")

level-size loop         matches on 1000 of 1000 trees
two lists               matches on 1000 of 1000 trees
(node, depth) pairs     matches on 1000 of 1000 trees
recursion, left first   matches on 1000 of 1000 trees
recursion, right first  matches on  108 of 1000 trees

Recursion matches only when it visits the left child first. Visiting the right child first reverses every level, so that version is right only on the 108 trees whose levels never hold more than one node.

The level-size loop is the usual choice in Python, Java and C++. In JavaScript the two-lists form is the tidiest, because it needs neither shift() nor a head index and lets each finished level go. Depth pairs suit code that needs each node’s depth for something else too, and recursion suits wide, shallow trees and code that is already recursive, as long as it visits the left child first and the tree is not deep enough to reach the recursion limit.

A level in the queue, or a path in the recursion

The choice matters most for memory. A queue holds at most the current level and the next one, while a recursive walk holds one path from the root. This program measures both on two shapes of tree:

"""What the queue and the recursion each hold at their peak, on a bushy tree and on a chain."""
import sys
from collections import deque


class Node:
    __slots__ = ("left", "right")

    def __init__(self):
        self.left = None
        self.right = None


def complete_tree(n):
    """n nodes in heap layout: node i has the children 2i + 1 and 2i + 2."""
    nodes = [Node() for _ in range(n)]
    for i in range(n):
        if 2 * i + 1 < n:
            nodes[i].left = nodes[2 * i + 1]
        if 2 * i + 2 < n:
            nodes[i].right = nodes[2 * i + 2]
    return nodes[0]


def chain(n):
    """n nodes, each the right child of the one before."""
    root = node = Node()
    for _ in range(n - 1):
        node.right = Node()
        node = node.right
    return root


def queue_sizes(root):
    """The number of levels, the widest level, and the most nodes the queue ever held."""
    levels = widest = peak = 0
    queue = deque([root])
    while queue:
        levels += 1
        widest = max(widest, len(queue))
        peak = max(peak, len(queue))
        for _ in range(len(queue)):
            node = queue.popleft()
            for child in (node.left, node.right):
                if child is not None:
                    queue.append(child)
            peak = max(peak, len(queue))
    return levels, widest, peak


def deepest_call(root):
    """How many calls deep a recursive depth-first walk goes."""
    def visit(node, depth):
        deepest = depth
        for child in (node.left, node.right):
            if child is not None:
                deepest = max(deepest, visit(child, depth + 1))
        return deepest

    return visit(root, 1)


for name, root in (("complete tree of 100,000 nodes", complete_tree(100_000)), ("chain of 1,500 nodes", chain(1_500))):
    levels, widest, peak = queue_sizes(root)
    try:
        recursion = f"{deepest_call(root):,} calls deep"
    except RecursionError:
        recursion = "RecursionError"
    print(f"{name}: {levels:,} levels, widest level {widest:,}, queue peak {peak:,}, recursion {recursion}")
print(f"recursion limit: {sys.getrecursionlimit():,} calls")

complete tree of 100,000 nodes: 17 levels, widest level 34,465, queue peak 50,000, recursion 17 calls deep
chain of 1,500 nodes: 1,500 levels, widest level 1, queue peak 1, recursion RecursionError
recursion limit: 1,000 calls

On the complete tree the widest level has 34,465 nodes, and the queue peaks at 50,000, half the tree. That is the moment when the whole last level has joined while 15,535 nodes of level 15 are still waiting. The recursion on the same tree is only 17 calls deep. On the chain it is the other way round: the queue never holds more than one node, but a recursive walk needs one call per node, and Python stops it with a RecursionError at its limit of 1,000 calls. Python’s documentation warns that raising the limit with sys.setrecursionlimit can crash the interpreter, so deep trees are better served by the queue. Wide, shallow trees favour recursion, and per-level answers can come from either. A long chain is the easiest deep tree to put in a test, which is why the exercise below includes one.

Signs that a problem wants level order

Reach for this template when a question is phrased in levels, rows or distance from the root:

• “For each level” or “each row”: lists, sums, averages or the largest value of every level.
• “The shallowest” or “the minimum depth”: the queue meets nodes in order of depth, so the first leaf it takes is the shallowest, and the walk can stop there, while a plain depth-first search has to visit every node to be sure.
• What can be seen from one side of the tree, or levels read in alternating directions.
• Positions within a level: widths, gaps, or linking each node to its neighbour on the right.
• Trees given as lists of children or as a parent table, where the same loop yields depths and level sizes.

The later lessons of this module take these one at a time.

Practise: the largest value on each level

The exercise asks for level_maxima(root), the largest value on each level. Two of its sample tests catch the usual slips: a tree whose values are all below zero, and a chain of 1,500 nodes that no recursive solution survives with Python’s default limit.

# 8 at the top; 4 and 11 below it; then 2, 6 and 14; then 5 (the sample tree of the lesson)
level_maxima(root)  # [8, 11, 14, 5]

from collections import deque


def level_maxima(root):
    """The largest value on each level of the tree, from the root's level down."""
    # Replace this line with your code.
    return []

from collections import deque

from maxima import level_maxima


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build(values):
    """A tree from its values in level order, with None where a child is missing."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root


def test_sample_tree():
    """the sample tree of the lesson"""
    assert level_maxima(build([8, 4, 11, 2, 6, None, 14, None, None, 5])) == [8, 11, 14, 5]


def test_empty_tree():
    """an empty tree has no levels"""
    assert level_maxima(None) == []


def test_single_node():
    """one node is one level"""
    assert level_maxima(Node(-4)) == [-4]


def test_values_below_zero():
    """every value is below zero, so no level's largest value is 0"""
    assert level_maxima(build([-3, -7, -1, None, -9, -2])) == [-3, -1, -2]


def test_levels_kept_apart():
    """a large value on a lower level does not leak into the level above"""
    assert level_maxima(build([1, 2, 3, 40, 5, 6, 7])) == [1, 3, 40]


def test_uneven_depths():
    """one branch stops early while the other goes on"""
    assert level_maxima(build([5, 9, 2, None, None, 1, 8, None, None, 3])) == [5, 9, 8, 3]


def test_wide_tree():
    """a complete tree of 4,095 nodes whose values are their positions in level order"""
    nodes = [Node(i) for i in range(4095)]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    # Level d holds the positions 2**d - 1 to 2**(d + 1) - 2, so its largest value is its last position.
    assert level_maxima(nodes[0]) == [2 ** (d + 1) - 2 for d in range(12)]


def test_deep_chain():
    """a chain of 1,500 nodes, one per level: deeper than a recursive solution can go by default"""
    root = node = Node(0)
    expected = [0]
    for i in range(1, 1500):
        child = Node(i * 37 % 101 - 50)
        if i % 2:
            node.right = child
        else:
            node.left = child
        node = child
        expected.append(child.val)
    assert level_maxima(root) == expected

Interview questions

Fresher · In the level-order template, why does for _ in range(len(queue)) handle exactly one level, even though the loop adds children to the queue while it runs?

Python evaluates range(len(queue)) once, when the for statement starts, so the loop runs as many times as the queue held nodes at that moment. At the start of a level the queue holds exactly that level: true for the root alone, and kept true because every node taken from the front adds its children at the back, behind the rest of its level. So the loop takes the whole current level and nothing else, and the children it added are exactly the next level, in order. Java and C++ get the same effect by reading queue.size() into a variable before the loop. A JavaScript loop written for (let i = 0; i < queue.length; i++) reads the length again before every iteration, so it runs on into the next level and mixes the levels up; store the length, or the end index, first.

Fresher · Breadth-first search on a graph keeps a visited set. Why does level-order traversal of a tree not need one?

A graph can reach the same node along several paths, and a cycle can lead back to a node already seen, so a graph search marks each node when it first adds it and skips it after that. A tree has neither problem: every node except the root has exactly one parent, and the walk follows edges only from parents to children, so each node is added to the queue once, by its parent, and the walk ends after n nodes. That is why the template needs nothing but the queue. The argument depends on following child links only. If the nodes also keep parent pointers and the walk follows those too, or the input is meant to be a tree but might contain a cycle, it is a graph search again and needs the visited set.

Key takeaways

• A queue gives level order because children join behind their whole level. When a level starts, the queue holds exactly that level, so its length is the level’s size.
• The template: read the queue’s length once, take that many nodes, add their children at the back, and record one answer per level. Time O(n); memory at most two levels.
• In JavaScript, never put queue.length in the level loop’s condition, and never drain a long queue with shift(): 2,499,950,000 moves on a tree of 100,000 nodes. Use a head index or a new array per level.
• Use collections.deque in Python, ArrayDeque in Java (it refuses null children) and std::queue in C++ (read front() before pop()).
• For an N-ary tree, add every child in order with one extend; the rest of the template stays the same.
• A queue holds a level and recursion holds a path: prefer the queue for deep, narrow trees, such as chains of 10⁵ nodes.