BST Traversal: Inorder, Preorder, Postorder, Level-Order

Key Insights

• Inorder traversal is the only traversal that produces sorted output from a BST, making it essential for validation and range queries
• The choice between recursive and iterative implementations matters: recursion is cleaner but risks stack overflow on deep trees, while iterative approaches give you explicit control
• Level-order traversal uses a queue (BFS) while the depth-first traversals (inorder, preorder, postorder) use a stack—understanding this distinction helps you pick the right tool for your problem

Introduction to BST Traversal

Tree traversal is one of those fundamentals that separates developers who understand data structures from those who just memorize LeetCode solutions. Every traversal method exists for a reason, and knowing when to use each one will save you hours of debugging and help you write more elegant solutions.

Binary Search Trees maintain the invariant that left children are smaller than the parent, and right children are larger. This property makes BSTs powerful for ordered data operations, but it also means the order in which you visit nodes dramatically affects what you can accomplish.

All four traversal methods visit every node exactly once, giving us O(n) time complexity. Space complexity varies: recursive approaches use O(h) stack space where h is tree height, while level-order uses O(w) where w is the maximum width of the tree.

Let’s start with a common node structure we’ll use throughout:

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

Inorder Traversal (Left → Root → Right)

Inorder traversal is the workhorse of BST operations. By visiting the left subtree first, then the current node, then the right subtree, you get nodes in sorted ascending order. This property is unique to inorder traversal and makes it invaluable for BST validation, finding the kth smallest element, and range queries.

The recursive implementation is straightforward:

def inorder_recursive(root: TreeNode) -> list[int]:
    result = []
    
    def traverse(node):
        if not node:
            return
        traverse(node.left)
        result.append(node.val)
        traverse(node.right)
    
    traverse(root)
    return result

The iterative version requires an explicit stack to simulate the call stack. The key insight is that you keep pushing left children until you can’t, then process the node and move right:

def inorder_iterative(root: TreeNode) -> list[int]:
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        
        # Process the node
        current = stack.pop()
        result.append(current.val)
        
        # Move to right subtree
        current = current.right
    
    return result

Use inorder when you need sorted output, when validating that a tree is actually a BST, or when implementing an iterator over tree elements.

Preorder Traversal (Root → Left → Right)

Preorder traversal processes the root before its children. This makes it perfect for tree serialization—you can reconstruct a BST from its preorder traversal because you always know the root comes first, followed by all left subtree nodes (smaller values), then right subtree nodes (larger values).

def preorder_recursive(root: TreeNode) -> list[int]:
    result = []
    
    def traverse(node):
        if not node:
            return
        result.append(node.val)
        traverse(node.left)
        traverse(node.right)
    
    traverse(root)
    return result

The iterative version is actually simpler than inorder because the processing order matches the natural stack behavior. Push right child first so left child gets processed first:

def preorder_iterative(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Preorder is your go-to for cloning trees, serializing tree structures to disk or network, and building expression trees where operators come before operands (prefix notation).

Postorder Traversal (Left → Right → Root)

Postorder processes children before parents. This is essential when you need to compute something from the bottom up—calculating subtree sizes, freeing memory during deletion, or evaluating expression trees where operands must be processed before operators.

def postorder_recursive(root: TreeNode) -> list[int]:
    result = []
    
    def traverse(node):
        if not node:
            return
        traverse(node.left)
        traverse(node.right)
        result.append(node.val)
    
    traverse(root)
    return result

The iterative version is trickier. One elegant approach uses two stacks—the second stack reverses the order:

def postorder_iterative_two_stacks(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    return [node.val for node in reversed(stack2)]

A single-stack approach tracks whether we’re visiting a node for the first time or returning from its right subtree:

def postorder_iterative_single_stack(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    stack = [(root, False)]
    
    while stack:
        node, visited = stack.pop()
        
        if visited:
            result.append(node.val)
        else:
            # Push in reverse order: node (visited), right, left
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    
    return result

Use postorder for tree deletion (you must delete children before parents), calculating directory sizes (sum children first), and evaluating postfix expressions.

Level-Order Traversal (BFS)

Level-order traversal is fundamentally different—it’s breadth-first rather than depth-first. Using a queue instead of a stack, it visits all nodes at depth d before any node at depth d+1.

from collections import deque

def level_order(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

Often you need nodes grouped by level. This variant tracks level boundaries:

def level_order_nested(root: 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

Level-order shines for finding minimum depth, calculating level averages, connecting nodes at the same level, and any problem where proximity to the root matters more than subtree structure.

Comparison and When to Use Each

Here’s a unified example demonstrating all four traversals on the same tree:

def demonstrate_traversals():
    #       4
    #      / \
    #     2   6
    #    / \ / \
    #   1  3 5  7
    
    root = TreeNode(4)
    root.left = TreeNode(2, TreeNode(1), TreeNode(3))
    root.right = TreeNode(6, TreeNode(5), TreeNode(7))
    
    print(f"Inorder:     {inorder_iterative(root)}")      # [1, 2, 3, 4, 5, 6, 7]
    print(f"Preorder:    {preorder_iterative(root)}")     # [4, 2, 1, 3, 6, 5, 7]
    print(f"Postorder:   {postorder_iterative_single_stack(root)}")  # [1, 3, 2, 5, 7, 6, 4]
    print(f"Level-order: {level_order(root)}")            # [4, 2, 6, 1, 3, 5, 7]

Practical Tips and Edge Cases

Always handle empty trees first. A null root should return an empty result, not crash:

def safe_traversal(root: TreeNode) -> list[int]:
    if not root:
        return []
    # ... rest of implementation

Single-node trees are valid edge cases—all four traversals should return the same single-element list.

For extremely deep trees (think 10,000+ levels), recursive implementations will hit Python’s default recursion limit. Either increase it with sys.setrecursionlimit() or use iterative implementations.

If you’re space-constrained, look into Morris traversal, which achieves O(1) space complexity by temporarily modifying tree pointers. It’s more complex but useful when memory is tight:

def morris_inorder(root: TreeNode) -> list[int]:
    result = []
    current = root
    
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                result.append(current.val)
                current = current.right
    
    return result

For wide trees (many nodes per level), level-order traversal’s queue can grow large. For deep, narrow trees, the depth-first approaches are more memory-efficient.

Master these four traversals and you’ll have the foundation to solve most tree problems. The pattern recognition becomes automatic: need sorted output? Inorder. Need to serialize? Preorder. Need bottom-up computation? Postorder. Need level-by-level processing? Level-order. Pick the right traversal, and the solution often writes itself.