Introduction

Iterating over a binary tree means visiting every node in a defined order. The four main traversal strategies are in-order (left, root, right), pre-order (root, left, right), post-order (left, right, root), and level-order (breadth-first). Each has distinct use cases — in-order produces sorted output from a BST, pre-order serializes the tree structure, post-order handles cleanup, and level-order processes nodes by depth. This article demonstrates both recursive and iterative implementations in Python.

Node Definition

1class TreeNode:
2    def __init__(self, val, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7# Example tree:
8#        4
9#       / \
10#      2   6
11#     / \ / \
12#    1  3 5  7
13root = TreeNode(4,
14    TreeNode(2, TreeNode(1), TreeNode(3)),
15    TreeNode(6, TreeNode(5), TreeNode(7))
16)

In-Order Traversal (Left, Root, Right)

Recursive:

1def inorder_recursive(node):
2    if node is None:
3        return []
4    return inorder_recursive(node.left) + [node.val] + inorder_recursive(node.right)
5
6print(inorder_recursive(root))  # [1, 2, 3, 4, 5, 6, 7]

Iterative (using a stack):

1def inorder_iterative(root):
2    result, stack = [], []
3    current = root
4    while current or stack:
5        while current:
6            stack.append(current)
7            current = current.left
8        current = stack.pop()
9        result.append(current.val)
10        current = current.right
11    return result
12
13print(inorder_iterative(root))  # [1, 2, 3, 4, 5, 6, 7]

In-order traversal of a BST yields values in sorted (ascending) order.

Pre-Order Traversal (Root, Left, Right)

Recursive:

1def preorder_recursive(node):
2    if node is None:
3        return []
4    return [node.val] + preorder_recursive(node.left) + preorder_recursive(node.right)
5
6print(preorder_recursive(root))  # [4, 2, 1, 3, 6, 5, 7]

Iterative:

1def preorder_iterative(root):
2    if not root:
3        return []
4    result, stack = [], [root]
5    while stack:
6        node = stack.pop()
7        result.append(node.val)
8        if node.right:
9            stack.append(node.right)
10        if node.left:
11            stack.append(node.left)
12    return result
13
14print(preorder_iterative(root))  # [4, 2, 1, 3, 6, 5, 7]

Pre-order is used to serialize/copy a tree because the root is processed before its children.

Post-Order Traversal (Left, Right, Root)

Recursive:

1def postorder_recursive(node):
2    if node is None:
3        return []
4    return postorder_recursive(node.left) + postorder_recursive(node.right) + [node.val]
5
6print(postorder_recursive(root))  # [1, 3, 2, 5, 7, 6, 4]

Iterative:

1def postorder_iterative(root):
2    if not root:
3        return []
4    result, stack = [], [root]
5    while stack:
6        node = stack.pop()
7        result.append(node.val)
8        if node.left:
9            stack.append(node.left)
10        if node.right:
11            stack.append(node.right)
12    return result[::-1]  # Reverse to get post-order
13
14print(postorder_iterative(root))  # [1, 3, 2, 5, 7, 6, 4]

Post-order is used for deleting trees (children are freed before the parent) and evaluating expression trees.

Level-Order Traversal (Breadth-First)

1from collections import deque
2
3def level_order(root):
4    if not root:
5        return []
6    result, queue = [], deque([root])
7    while queue:
8        level = []
9        for _ in range(len(queue)):
10            node = queue.popleft()
11            level.append(node.val)
12            if node.left:
13                queue.append(node.left)
14            if node.right:
15                queue.append(node.right)
16        result.append(level)
17    return result
18
19print(level_order(root))  # [[4], [2, 6], [1, 3, 5, 7]]

Level-order processes all nodes at depth d before any node at depth d+1. It uses a queue instead of a stack.

Traversal Comparison

Common Pitfalls

• Using recursion on very deep trees: Python's default recursion limit is 1000. A skewed tree with 10,000 nodes causes RecursionError. Use iterative traversal with an explicit stack for production code, or increase the limit with sys.setrecursionlimit().
• Pushing children in wrong order for pre-order iterative: In the stack-based pre-order, push the right child before the left. Since a stack is LIFO, the left child is popped first, producing the correct root-left-right order.
• Confusing in-order sorted output with any binary tree: In-order traversal only produces sorted output for a Binary Search Tree. For a general binary tree, in-order output has no guaranteed ordering.
• Modifying the tree during traversal: Inserting or deleting nodes while iterating can cause skipped nodes or infinite loops. Collect nodes into a list first, then modify the tree.
• Forgetting the base case in recursive traversal: Omitting if node is None: return causes AttributeError when accessing .left or .right on None. Always check for None before recursing.

Summary

• In-order (left, root, right) yields sorted values from a BST — use for ordered processing
• Pre-order (root, left, right) visits the root first — use for tree serialization and copying
• Post-order (left, right, root) visits the root last — use for deletion and expression evaluation
• Level-order (breadth-first) processes level by level using a queue
• Iterative traversals use an explicit stack (or queue) and avoid recursion depth limits
• All four traversals visit every node exactly once with O(n) time and O(h) or O(w) space