Binary Tree Level Order Traversal
Problem statement
Given the root of a binary tree, return its values grouped by level. The first group holds the root's value, the second group holds the values one step below the root, and so on. Inside a group, list the values from left to right.
An empty tree gives an empty list. In the examples a tree is written in level order, with null for a missing child.
Examples
Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Explanation: The tree has 3 at the top. Its children are 9 on the left and 20 on the right. Node 9 has no children, and node 20 has children 15 and 7. So the levels are [3], then [9, 20], then [15, 7].
Example 2
Input: root = [1]
Output: [[1]]
Explanation: A tree with only a root has a single level that holds one value.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no nodes, so there are no levels and the result is an empty list.
Hints
Approach
Optimal: DFS with depth
Intuition
You do not need a queue if every node knows its own depth. Walk the tree depth first and pass the depth down: the root is at depth 0, its children at depth 1, and so on. Keep the result as a list of groups, where group number d holds the values at depth d. When you reach a node at a depth that has no group yet, create an empty group first. Then append the node's value to the group for its depth. If you always go to the left child before the right child, each group fills from left to right, so the order is correct. This uses the call stack instead of a queue, which can save memory on a tall, thin tree.
Steps
- Start with an empty result list.
- Write a helper
walk(node, depth). Ifnodeis empty, return. - If
depthequals the number of groups in the result, add a new empty group. - Append the node's value to the group at index
depth. - Call
walk(left, depth + 1), thenwalk(right, depth + 1). - Call
walk(root, 0)and return the result.
Dry run
root = [3, 9, 20, null, null, 15, 7]
| visit | depth | new group made? | result after |
|---|---|---|---|
| 3 | 0 | yes | [[3]] |
| 9 | 1 | yes | [[3], [9]] |
| 20 | 1 | no | [[3], [9, 20]] |
| 15 | 2 | yes | [[3], [9, 20], [15]] |
| 7 | 2 | no | [[3], [9, 20], [15, 7]] |
Node 9 has no children, so the walk goes straight back up and then into 20. The result is [[3], [9, 20], [15, 7]].
Edge cases: an empty tree returns at once and the result stays []. A tree with only a root creates one group and returns [[1]].
Complexity
Time O(n) - Every node is visited exactly once, and each visit does a constant amount of work: check the depth, append the value and make two recursive calls. So the total is proportional to the number of nodes.
Space O(h) - Here h is the height of the tree. Only the recursion stack is used, besides the answer itself, and it is as deep as the tree is tall. For a balanced tree that is about log n. For a tree that is one long chain it is n.
from collections import deque
from typing import Optional
# LeetCode already provides TreeNode. It is defined here so the page runs as-is.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
result = []
def walk(node, depth: int) -> None:
if node is None:
return
if depth == len(result): # first node seen at this depth
result.append([])
result[depth].append(node.val)
walk(node.left, depth + 1) # left before right keeps each level in order
walk(node.right, depth + 1)
walk(root, 0)
return result
def build(values):
"""Build a tree from a level-order list where None means a missing child."""
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue, i = deque([root]), 1
while queue and i < len(values):
node = queue.popleft()
if i < len(values):
if values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values):
if values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
if __name__ == "__main__":
print(Solution().levelOrder(build([3, 9, 20, None, None, 15, 7])))
print(Solution().levelOrder(build([1])))
print(Solution().levelOrder(build([])))RecapThe whole problem in a few lines, for the night before
- Spot it: tree values wanted grouped level by level
- Idea: BFS with a queue; read the queue size before each level and take out exactly that many nodes
- Cost: O(n) time, O(w) space where w is the widest level
- Trap: reading the size inside the loop mixes levels together; an empty tree returns
[]
Interview follow-ups
Return the levels bottom-up, or in zigzag order (left to right, then right to left).
For bottom-up, run the same level-by-level search and reverse the list of levels at the end, which costs O(n). For zigzag, keep a boolean that flips after each level. When it says right to left, reverse that level's list before adding it, or build it with a double-ended queue. The queue still holds nodes in left to right order. Both versions keep O(n) time.
Return the average value of each level.
Keep the same queue loop. While you take out the
knodes of a level, add their values to a runningtotalinstead of a list. After the loop, appendtotal / kto the result. Use a floating point result, and watch for integer overflow in the sum in Java and C++ by using a 64-bit total. Time is O(n) and space is O(w).
Frequently asked questions
Children are pushed onto the same queue while you process the level. If you checked the size on every iteration, the loop would keep going into the next level and mix the levels together. Capturing the size first draws the boundary between levels.
Start with BFS. It matches the name of the problem, and most interviewers expect to see the queue and the size trick. Mention the DFS version as an alternative: it has the same O(n) time and uses O(h) stack space instead of O(w) queue space. That can be smaller on a tall, thin tree and larger on a very deep one, where recursion can overflow the stack.
A missing child simply adds nothing to its level and pushes nothing to the queue. In Example 1 the node 9 has no children, so level 3 only contains the children of 20. The result has no placeholder for the gaps.
Breadth-first order is how you roll changes out in waves: first the root, then every direct dependant, then the next ring. It is also how you find everything within N hops of a host, or group an org chart or dependency tree by distance.
