Binary Tree Level Order Traversal

The problem

You are given the root of a binary tree. Return the values of its nodes level by level. The first list holds the root, the next list holds its children, and so on. Inside each level, list the values from left to right.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [3, 8, 5, null, 6, 2, 9, 4]

Output: [[3], [8, 5], [6, 2, 9], [4]]

The tree has four levels. 6 is the right child of 8, and 4 is the left child of 6.

Example 2

Input: root = [1]

Output: [[1]]

One node, so one level.

Example 3

Input: root = []

Output: []

An empty tree has no levels.

Constraints

• The tree has n nodes, where 0 ≤ n ≤ 2,000.
• -1,000 ≤ Node.val ≤ 1,000

Clarifying questions

Do we return one flat list or one list per level?

One list per level. So we must know where each level ends.

What does an empty tree return?

An empty list, with no levels in it.

Should a missing child leave a gap?

No. Only real nodes appear. A level just has fewer values.

Is the order inside a level fixed?

Yes, left to right, as the nodes appear on the page.

Spot the pattern

“Level by level” means all nodes at one distance from the root come before any node further away. That is breadth-first search (BFS): explore everything one step away, then two steps, and so on. BFS uses a queue, a line where the first node in is the first node out. It is the tree version of the graph search pattern.

Solutions

Breadth-first searchO(n)

Show all

There is only one approach worth showing. Every value must be read, so no method can beat n steps, and BFS gives each node exactly one visit.

Breadth-first search O(n)

The idea

Put the root in a queue. Then repeat: take a node from the front, write down its value, and put its children at the back. Because the queue is first in, first out, a node’s children always wait behind every node of the current level.

To split the output into levels, look at the queue size at the start of each round. At that moment the queue holds exactly one whole level. So take exactly that many nodes. The children added during the round are the next level, and they wait for the next round.

Why it is correct: the queue only ever holds the rest of one level, followed by the start of the next. Nodes come out in level order and left to right, and counting the size cuts the output at each level boundary.

Walkthrough

queue front →

3

level

empty

result

empty

1. if root is None: return []
2. result, queue = [], deque([root])
3. while queue:
4. level = []
5. for _ in range(len(queue)):
6. node = queue.popleft()
7. level.append(node.val)
8. if node.left: queue.append(node.left)
9. if node.right: queue.append(node.right)
10. result.append(level)
11. return result

Put the root in the queue. A queue hands nodes out in the order they came in, so the tree comes out level by level. Nodes marked q are waiting in the queue.

← BackStep →Play1 / 17

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Breadth-first search with a queue: the queue holds one level at a
    // time, in left-to-right order. Each node goes in and out once, so n steps.
    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()) {
            List<Integer> level = new ArrayList<>();
            // Right now the queue holds exactly one whole level. Take only
            // that many, so the children we add wait for the next round.
            for (int size = queue.size(); size > 0; size--) {
                TreeNode node = queue.poll();
                level.add(node.val);
                // Left before right keeps the next level in order.
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines take one node out, write it down and push its children. They sit inside two loops, but together the loops only ever take nodes out of the queue. Each run is a fixed job: one pop, one append, up to two pushes. So each run counts as 1 step.

   1. if root is None: return []
   2. result, queue = [], deque([root])
   3. while queue:
   4. level = []
   5. for _ in range(len(queue)):
   6. node = queue.popleft()
   7. level.append(node.val)
   8. if node.left: queue.append(node.left)
   9. if node.right: queue.append(node.right)
   10. result.append(level)
   11. return result

2. 2 Count the runs on Example 1

   The table counts pops and pushes per level. Every node is popped once: 1 + 2 + 3 + 1 = 7. Every node is pushed once too: the root at the start, then 6 children along the way.

   7 runs of the inner loop, one per node.

   level	0	1	2	3	total
   nodes	3	8, 5	6, 2, 9	4
   pops	1	2	3	1	7
   pushes	2	3	1	0	6 + root = 7

3. 3 Write the count for any n

   The inner loop runs once per node taken out of the queue. A node goes in only once, when its parent is taken out, so it comes out only once. With n nodes:

   n runs

   Check it with Example 1: n = 7, and the inner loop ran 7 times.

4. 4 Keep only the part that grows fastest

   The count is already n, so there is nothing to drop. The outer loop does not add a factor: it only splits the same n runs into levels.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The queue holds at most one level plus part of the next. The widest level of a full binary tree is its bottom row, about n / 2 nodes. Halving does not change the growth, so the queue needs up to O(n) space. The answer itself also holds all n values, but it is the required output.

   queue (one level at a time)level

Common mistake

Reading the queue size inside the loop

If the loop checks len(queue) on every run, it sees the children that were just added, and the levels run together. Read the size once, before the round starts.

Tested at the limits

2,000 random trees of 0 to 12 nodes, in every shape. The breadth-first search gave the same levels every time as a simple check that walks depth-first and puts each value in the list for its depth.

Largest inputs	Result
2,000 nodes (the most allowed), balanced. Breadth-first search.	Under 0.001 s, and about 0.03 MB of extra memory: the queue and the answer, which is the O(n) space.
2,000 nodes in one long line, so 2,000 levels. Breadth-first search.	Under 0.001 s, and about 0.2 MB of extra memory: the answer holds 2,000 small lists, one per level.