Skip to main content
DSA patterns

Binary Tree Level Order Traversal

mediumTrees Must-do

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

Hint 1: A queue returns items in the order they were added. That is exactly the left to right, level by level order we need.

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

  1. Start with an empty result list.
  2. Write a helper walk(node, depth). If node is empty, return.
  3. If depth equals the number of groups in the result, add a new empty group.
  4. Append the node's value to the group at index depth.
  5. Call walk(left, depth + 1), then walk(right, depth + 1).
  6. 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 k nodes of a level, add their values to a running total instead of a list. After the loop, append total / k to 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.