LeetCode 102: Binary Tree Level Order Traversal

Problem Restatement

We are given the root of a binary tree.

We need to return the node values level by level, from left to right inside each level. The official problem asks for the level order traversal of the binary tree’s node values.

For this tree:

        3
      /   \
     9     20
          /  \
         15   7

The answer is:

[[3], [9, 20], [15, 7]]

Each inner list contains one tree level.

Input and Output

LeetCode gives the TreeNode class:

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

The function shape is:

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        ...

Examples

Consider this tree:

        3
      /   \
     9     20
          /  \
         15   7

Level 0 contains only the root:

[3]

Level 1 contains the children of 3:

[9, 20]

Level 2 contains the children of 9 and 20, from left to right:

[15, 7]

So the final answer is:

[[3], [9, 20], [15, 7]]

For a single-node tree:

1

The answer is:

[[1]]

For an empty tree:

[]

The answer is:

[]

First Thought: Traverse by Depth

We need all nodes at depth 0, then all nodes at depth 1, then all nodes at depth 2, and so on.

This order suggests breadth-first search.

Depth-first search goes down one path before coming back.

Breadth-first search processes the tree one layer at a time.

A queue is the natural data structure for this because the first node inserted should be the first node processed.

Key Insight

At any moment, the queue can hold all nodes from the current level.

Before processing a level, record the queue size.

That size tells us exactly how many nodes belong to the current level.

For example, if the queue contains:

[9, 20]

then the current level has size 2.

We process exactly two nodes, collect their values, and append their children to the queue for the next level.

This keeps level boundaries clean.

Algorithm

If root is None, return an empty list.

Otherwise:

1. Create a queue and put root into it.
2. Create an empty result list.
3. While the queue is not empty:
   1. Read the current queue size.
   2. Create an empty list for this level.
   3. Process exactly that many nodes.
   4. Append each node value to the current level list.
   5. Add the node’s left child if it exists.
   6. Add the node’s right child if it exists.
   7. Append the level list to the result.
4. Return the result.

Correctness

The queue starts with the root, so the first processed level is level 0.

At the start of each loop, the queue contains exactly the nodes of the current level, ordered from left to right.

We store the queue size before adding children. Therefore, the loop processes only nodes from the current level. Children added during this loop belong to the next level, so they wait in the queue until the next outer loop iteration.

For each node, we append the left child before the right child. This preserves left-to-right order for the next level.

By induction over the tree levels, every level is appended to the result in top-to-bottom order, and every node inside each level appears from left to right. Therefore, the algorithm returns the required level order traversal.

Complexity

Here, n is the number of nodes in the tree.

The output itself also stores n values.

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# 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]]:
        if root is None:
            return []

        ans = []
        q = deque([root])

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        return ans

Code Explanation

We first handle the empty tree:

if root is None:
    return []

Then we create the answer list and the queue:

ans = []
q = deque([root])

The queue starts with the root because level order traversal begins at the root.

The outer loop runs while there are still nodes to process:

while q:

For each level, we create a fresh list:

level = []

This loop is the important part:

for _ in range(len(q)):

len(q) is measured before the loop starts. That gives the number of nodes currently in this level.

Inside the loop, we remove the next node:

node = q.popleft()

Then we store its value:

level.append(node.val)

After that, we add its children for the next level:

if node.left is not None:
    q.append(node.left)

if node.right is not None:
    q.append(node.right)

After all nodes of the current level are processed, we append the level to the answer:

ans.append(level)

Finally:

return ans

Testing

from collections import deque
from typing import Optional

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]]:
        if root is None:
            return []

        ans = []
        q = deque([root])

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        return ans

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.levelOrder(root1) == [[3], [9, 20], [15, 7]]

    root2 = TreeNode(1)
    assert s.levelOrder(root2) == [[1]]

    root3 = None
    assert s.levelOrder(root3) == []

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), None),
        TreeNode(3, None, TreeNode(5)),
    )
    assert s.levelOrder(root4) == [[1], [2, 3], [4, 5]]

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3, TreeNode(4))),
        None,
    )
    assert s.levelOrder(root5) == [[1], [2], [3], [4]]

    print("all tests passed")

run_tests()

Test meaning: