Solving Binary Tree Level Order Traversal in Python: Step-by-Step Guide

Introduction to Binary Tree Level Order Traversal

Binary Tree Level Order Traversal is one of the most fundamental algorithms every developer should master. It is a classic Breadth-First Search (BFS) technique that visits nodes of a binary tree level by level, from top to bottom, and from left to right within each level. Unlike depth-first traversals (inorder, preorder, postorder) that dive deep into one branch before backtracking, level order traversal explores the tree horizontally.

This algorithm frequently appears in technical interviews at companies like Google, Amazon, and Microsoft because it tests your understanding of both tree data structures and queue-based algorithms. Beyond interviews, it has practical applications in serialization, pretty-printing trees, finding the shortest path in unweighted graphs, and processing hierarchical data.

What Is Level Order Traversal?

Given a binary tree, level order traversal returns the node values grouped by their depth. Consider the following tree:

The level order traversal would produce [[3], [9, 20], [15, 7]]. Each inner list represents a single level of the tree. The root sits at level 0, its children at level 1, and so on.

Key Characteristics

BFS-based: Uses a queue (FIFO) to track nodes awaiting processing.
Level-aware: Maintains knowledge of where one level ends and the next begins.
Time complexity: O(n), where n is the number of nodes, since each node is processed exactly once.
Space complexity: O(n) in the worst case for the queue, particularly for a perfectly balanced tree where the last level holds roughly n/2 nodes.

Why It Matters

Understanding level order traversal unlocks several advanced tree and graph problems. Many real-world scenarios involve hierarchical data: organizational charts, file systems, DOM trees, and decision trees in machine learning. Processing these structures level by level is often the most natural approach.

Specific use cases include:

Tree serialization and deserialization: Storing a tree in a flat format and reconstructing it later.
Right-side or left-side view of a tree: Capturing the last or first node at each level.
Zigzag traversal: Alternating the direction of traversal at each level.
Level-wise aggregation: Computing averages, sums, or maximum values per level.
Shortest path problems: BFS finds the shortest path in unweighted graphs, and trees are a special case.

Setting Up the Binary Tree

Before implementing the traversal, we need a binary tree node class. In Python, this is typically defined as a simple class with a value and left/right child references.

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

# Build the example tree
#        3
#       / \
#      9  20
#        /  \
#       15   7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

This structure allows us to construct any binary tree by linking TreeNode instances together. With the tree ready, we can now implement the traversal.

Step-by-Step Implementation

Step 1: Initialize the Queue

The core data structure is a queue. We use Python's collections.deque because it offers O(1) append and pop operations from both ends, unlike a regular list which has O(n) cost for popping from the front.

from collections import deque

def levelOrder(root):
    if not root:
        return []

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

We handle the edge case of an empty tree immediately by returning an empty list. Otherwise, we seed the queue with the root node and prepare an empty result list to collect levels.

Step 2: Process Level by Level

The trick to distinguishing levels is to capture the current queue length before processing any nodes. That length tells us exactly how many nodes belong to the current level. We then process exactly that many nodes, collecting their values and enqueuing their children.

    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

Each iteration of the outer while loop handles one complete level. The inner for loop drains exactly the nodes that were in the queue at the start of that level, ensuring children added during the loop do not bleed into the current level's processing.

Step 3: Complete Function

Putting it all together, here is the complete, runnable implementation:

from collections import deque

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

def levelOrder(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

# Test it
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(levelOrder(root))
# Output: [[3], [9, 20], [15, 7]]

Alternative Approach: Recursive DFS

While the queue-based BFS is the most intuitive solution, you can also solve this problem recursively using depth-first search. The idea is to track the current depth and append each node's value to the corresponding level list.

def levelOrderRecursive(root):
    result = []

    def dfs(node, depth):
        if not node:
            return
        if len(result) == depth:
            result.append([])
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result

This approach has the same O(n) time complexity but uses O(h) of recursion stack space, where h is the height of the tree. It can be more elegant but risks stack overflow on extremely deep trees. The iterative BFS approach is generally preferred in production code.

Common Variations

Zigzag Level Order Traversal

In this variation, you reverse the direction at every alternate level. Simply reverse the current_level list before appending it when the level index is odd.

def zigzagLevelOrder(root):
    if not root:
        return []

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

    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)

        if not left_to_right:
            current_level.reverse()
        result.append(current_level)
        left_to_right = not left_to_right

    return result

Right Side View

To get the right side view of a tree, simply capture the last node's value at each level instead of collecting all values.

def rightSideView(root):
    if not root:
        return []

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

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

Level Averages

Computing the average value at each level is straightforward once you have the level-by-level structure.

def averageOfLevels(root):
    if not root:
        return []

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

    while queue:
        level_size = len(queue)
        level_sum = 0

        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_sum / level_size)

    return result

Best Practices

Always handle the empty tree case: Returning an empty list early prevents unnecessary work and avoids errors when accessing root.val.
Use deque instead of lists for queues: List pop(0) is O(n), which degrades performance significantly on large trees. deque.popleft() is O(1).
Capture level size before processing: A common mistake is to iterate over the queue while modifying it, which mixes levels together. Always snapshot len(queue) at the start of each level.
Prefer iterative BFS for production: Recursive DFS solutions are elegant but can hit Python's recursion limit (default 1000) on skewed trees. Iterative approaches avoid this risk entirely.
Test edge cases: Verify your solution against an empty tree, a single-node tree, a left-skewed tree, a right-skewed tree, and a perfectly balanced tree.
Consider memory usage: For very wide trees, the queue can grow large. If you only need the last level or a specific level, consider early termination or a two-pointer approach.

Performance Analysis

Both the iterative BFS and recursive DFS solutions visit every node exactly once, giving them O(n) time complexity. The difference lies in space usage. The iterative approach uses O(w) space for the queue, where w is the maximum width of the tree. The recursive approach uses O(h) space for the call stack, where h is the height.

For a balanced tree, w is approximately n/2 at the bottom level, and h is log(n). For a skewed tree, w is 1 and h is n. In practice, the iterative BFS is more predictable and safer for arbitrary tree shapes, making it the recommended default.

Conclusion

Binary Tree Level Order Traversal is a foundational algorithm that every Python developer should be able to implement confidently. By leveraging a queue and snapshotting the level size before processing each level, you can cleanly separate nodes into their respective depth groups. The same pattern extends naturally to variations like zigzag traversal, right side view, and level-wise aggregation. Mastering this technique not only prepares you for technical interviews but also equips you with a versatile tool for processing hierarchical data in real-world applications. Practice the core implementation until it becomes second nature, then explore the variations to deepen your understanding of breadth-first thinking.