LeetCode 102 - Binary Tree Level Order Traversal

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to perform a level order traversal on a binary tree. A binary tree is a hierarchical structure where each node can have at most two children, commonly referred to as the left child and the right child.

A level order traversal means we visit the tree one level at a time, starting from the root. Within the same level, nodes are processed from left to right. Instead of returning a single flat list of values, we must return a nested list where each inner list contains all node values at a specific depth.

For example, given the tree:

The traversal proceeds level by level:

Level 0 contains node 3
Level 1 contains nodes 9 and 20
Level 2 contains nodes 15 and 7

The result becomes:

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

The input is the root node of a binary tree. The output must be a list of lists, where each nested list represents one level of the tree.

The constraints tell us that the tree can contain up to 2000 nodes. This is small enough that an O(n) traversal is easily efficient enough, but large enough that inefficient repeated traversals should be avoided. The node values themselves are not important for algorithmic complexity because they are simple integers in a small range.

Several edge cases are important:

The tree may be empty, meaning root is None in Python or nil in Go. In that case, the answer should be an empty list.
The tree may contain only one node.
The tree may be highly unbalanced, effectively becoming a linked list.
Some nodes may have only one child.

A correct implementation must handle all of these situations without errors.

Approaches

Brute Force Approach

A brute force solution would first determine the height of the tree, then process one level at a time using a recursive helper function.

The algorithm would work like this:

Compute the maximum depth of the tree.
For each depth from 0 to height - 1, recursively traverse the tree and collect all nodes at that depth.
Append the collected nodes into the final result.

This approach is correct because every level is explicitly traversed and collected independently. However, the major drawback is that the tree is repeatedly traversed for every level.

In the worst case, such as a skewed tree with height n, each level traversal may visit nearly all nodes again. This leads to O(n^2) time complexity.

Optimal Approach

The key insight is that level order traversal naturally matches Breadth-First Search, commonly abbreviated as BFS.

BFS processes nodes in the exact order required by the problem:

Visit all nodes at the current depth
Then move to the next depth
Process nodes from left to right

A queue is the ideal data structure for BFS because it processes elements in first-in, first-out order.

The algorithm starts by placing the root into the queue. Then, while the queue is not empty:

Determine how many nodes belong to the current level
Remove exactly that many nodes from the queue
Record their values
Add their children into the queue for the next iteration

Each node is visited exactly once, giving an efficient O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly traverses the tree for each level
Optimal	O(n)	O(n)	Uses BFS with a queue, visits each node once

Algorithm Walkthrough

Optimal BFS Algorithm

Start by checking whether the tree is empty. If the root is None, return an empty list immediately because there are no levels to traverse.
Create a queue and insert the root node into it. The queue will help process nodes level by level in the correct order.
Initialize an empty result list. This will eventually store all levels of the tree.
Begin a loop that continues while the queue is not empty. Each iteration of this loop processes exactly one level of the tree.
At the start of each iteration, determine the current queue size. This value represents how many nodes belong to the current level because all nodes for the current level were added during the previous iteration.
Create an empty list called current_level to store node values for this level.
Process exactly level_size nodes:
Remove the front node from the queue.
Add its value to current_level.
If the node has a left child, add it to the queue.
If the node has a right child, add it to the queue.
After processing all nodes for the current level, append current_level to the result list.
Continue until the queue becomes empty, meaning all nodes in the tree have been processed.
Return the final result list.

Why it works

The algorithm maintains an important invariant: before processing a level, the queue contains exactly all nodes belonging to that level, in left-to-right order.

By recording the queue size before processing begins, we ensure that only nodes from the current level are removed during that iteration. Any children added during processing belong to the next level and are processed later.

Because every node is visited once and placed into exactly one level list, the algorithm correctly produces the required level order traversal.

Python Solution

from collections import deque
from typing import List, 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 not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

The implementation begins by handling the empty tree case. Returning immediately prevents unnecessary processing and avoids queue errors.

A deque is used because it provides efficient O(1) insertion and removal from both ends. Using a normal Python list for queue operations would make removals from the front inefficient.

The queue initially contains only the root node. The outer while loop processes one tree level at a time.

Inside the loop, level_size captures how many nodes belong to the current level. This is critical because new child nodes will be added during traversal, and we do not want them mixed into the current level.

The inner loop processes exactly those nodes. Each node's value is added to current_level, and its children are added to the queue for future processing.

After finishing the level, the collected values are appended to the final result.

Once the queue becomes empty, every node has been processed, and the complete traversal is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            currentLevel = append(currentLevel, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}

The Go implementation follows the same BFS logic as the Python solution.

The primary difference is queue handling. Go does not provide a built-in deque structure, so a slice is used as the queue. Removing the first element is done with:

queue = queue[1:]

The implementation also explicitly checks for nil instead of Python's truthy checks.

Go slices dynamically resize as elements are appended, making them suitable for BFS traversal queues.

Worked Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Tree structure:

Initial state:

Variable	Value
queue	[3]
result	[]

Level 0

Operation	queue	current_level
Remove 3	[]	[3]
Add 9	[9]	[3]
Add 20	[9, 20]	[3]

After level completion:

result = [[3]]

Level 1

Operation	queue	current_level
Remove 9	[20]	[9]
Remove 20	[]	[9, 20]
Add 15	[15]	[9, 20]
Add 7	[15, 7]	[9, 20]

After level completion:

result = [[3], [9, 20]]

Level 2

Operation	queue	current_level
Remove 15	[7]	[15]
Remove 7	[]	[15, 7]

Final result:

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

Example 2

Input:

root = [1]

Initial state:

Variable	Value
queue	[1]
result	[]

Processing:

Operation	queue	current_level
Remove 1	[]	[1]

Final result:

[[1]]

Example 3

Input:

root = []

Since the root is None, the algorithm immediately returns:

[]

No queue or traversal is needed.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(n)	The queue may contain up to one full level of the tree

The time complexity is linear because each node enters and leaves the queue exactly once.

The space complexity is also linear in the worst case. A complete binary tree can have roughly n/2 nodes at the final level, meaning the queue may temporarily store a large fraction of all nodes.

Test Cases

from collections import deque

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):
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

solution = Solution()

# Example 1, balanced tree
root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)

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

# Example 2, single node tree
root2 = TreeNode(1)

assert solution.levelOrder(root2) == [[1]]

# Example 3, empty tree
assert solution.levelOrder(None) == []

# Left skewed tree
root4 = TreeNode(1)
root4.left = TreeNode(2)
root4.left.left = TreeNode(3)

assert solution.levelOrder(root4) == [[1], [2], [3]]

# Right skewed tree
root5 = TreeNode(1)
root5.right = TreeNode(2)
root5.right.right = TreeNode(3)

assert solution.levelOrder(root5) == [[1], [2], [3]]

# Complete binary tree
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.right = TreeNode(3)
root6.left.left = TreeNode(4)
root6.left.right = TreeNode(5)
root6.right.left = TreeNode(6)
root6.right.right = TreeNode(7)

assert solution.levelOrder(root6) == [
    [1],
    [2, 3],
    [4, 5, 6, 7]
]

# Tree with missing children
root7 = TreeNode(1)
root7.left = TreeNode(2)
root7.right = TreeNode(3)
root7.left.right = TreeNode(4)

assert solution.levelOrder(root7) == [
    [1],
    [2, 3],
    [4]
]

Test	Why
Balanced tree	Verifies standard multi-level traversal
Single node tree	Ensures simplest non-empty case works
Empty tree	Confirms early return logic
Left skewed tree	Tests unbalanced tree behavior
Right skewed tree	Verifies handling of missing left children
Complete binary tree	Tests wide levels with many nodes
Tree with missing children	Ensures sparse trees are processed correctly

Edge Cases

Empty Tree

An empty tree is represented by root = None in Python or root == nil in Go. This case is easy to overlook because attempting to access children of a null root would cause runtime errors.

The implementation handles this immediately with an early return:

if not root:
    return []

This guarantees safe execution even when no nodes exist.

Highly Unbalanced Tree

A tree may resemble a linked list, where every node has only one child. For example:

Some recursive approaches risk deep recursion depth issues, but the BFS queue-based solution handles this naturally. Each level simply contains one node, and the algorithm still visits every node exactly once.

Sparse Trees with Missing Children

Many binary trees are incomplete, meaning some nodes have only one child.

For example:

A buggy implementation might incorrectly assume both children exist or accidentally insert null values into the queue.

This implementation explicitly checks whether each child exists before appending it:

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

As a result, only valid nodes are processed, and sparse trees work correctly.