Data Structures
  • Master inorder (left, root, right), preorder (root, left, right), postorder (left, right, root)
  • Implement iterative traversals with explicit stacks
  • Use level-order (BFS) for breadth-first processing with queues

Tree Traversals

You have a binary tree. Now you need to visit all nodes. But in what order?

Different orders give different results. And different problems need different orders.

What's Traversal?

Visiting every node in the tree exactly once. The order matters.

Three classic recursive traversals:

  • Inorder (left, root, right)
  • Preorder (root, left, right)
  • Postorder (left, right, post)

Plus level-order (breadth-first).

Inorder Traversal (Left, Root, Right)

Process left subtree, then root, then right subtree.

def inorder(node):
    if node is None:
        return
    
    inorder(node.left)
    print(node.value)
    inorder(node.right)

Example tree:

    4
   / \
  2   6
 / \ / \
1  3 5  7

Inorder: 1, 2, 3, 4, 5, 6, 7

Left subtree of 4 is tree rooted at 2. Inorder of that: 1, 2, 3. Then root 4. Then right subtree: 5, 6, 7.

Why inorder? For Binary Search Trees (BST), inorder gives sorted order. That's huge.

Preorder Traversal (Root, Left, Right)

Process root first, then left subtree, then right subtree.

def preorder(node):
    if node is None:
        return
    
    print(node.value)
    preorder(node.left)
    preorder(node.right)

Same tree: 4, 2, 1, 3, 6, 5, 7

Root 4 first. Then left subtree preorder: 2, 1, 3. Then right subtree preorder: 6, 5, 7.

Why preorder? Copying a tree. Process root (create copy), then copy children. Also useful for prefix expressions.

Postorder Traversal (Left, Right, Root)

Process left subtree, then right subtree, then root.

def postorder(node):
    if node is None:
        return
    
    postorder(node.left)
    postorder(node.right)
    print(node.value)

Same tree: 1, 3, 2, 5, 7, 6, 4

Left subtree postorder: 1, 3, 2. Right subtree postorder: 5, 7, 6. Then root 4.

Why postorder? Deleting a tree. Delete children before parent. Also for evaluating expression trees.

Level-Order Traversal (BFS)

Visit nodes level by level, left to right.

Use a queue.

from collections import deque

def level_order(root):
    if root is None:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Same tree: 4, 2, 6, 1, 3, 5, 7

Level 0: 4. Level 1: 2, 6. Level 2: 1, 3, 5, 7.

Why level-order? Finding shortest path (in unweighted tree), printing tree by levels, checking completeness.

Iterative Inorder (Stack)

Recursive uses call stack implicitly. You can use explicit stack.

def inorder_iterative(root):
    stack = []
    current = root
    
    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Current is None, pop from stack
        current = stack.pop()
        print(current.value)
        
        # Visit right subtree
        current = current.right

Pushes all left nodes to stack. Pops, processes, then visits right.

Iterative Preorder (Stack)

def preorder_iterative(root):
    if root is None:
        return
    
    stack = [root]
    
    while stack:
        node = stack.pop()
        print(node.value)
        
        # Push right first, then left (stack is LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Process root, push right then left (so left is popped first).

Iterative Postorder (Two Stacks)

Postorder is tricky iteratively. Use two stacks.

def postorder_iterative(root):
    if root is None:
        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)
    
    # Stack2 has nodes in reverse postorder
    while stack2:
        print(stack2.pop().value)

Or use one stack with visited tracking (more complex).

Morris Traversal (No Stack, No Recursion)

O(1) space inorder traversal using threading.

def morris_inorder(root):
    current = root
    
    while current:
        if current.left is None:
            print(current.value)
            current = current.right
        else:
            # Find inorder predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if predecessor.right is None:
                # Create thread
                predecessor.right = current
                current = current.left
            else:
                # Remove thread
                predecessor.right = None
                print(current.value)
                current = current.right

Temporarily modifies tree (creates threads), then restores. O(n) time, O(1) space. Clever but complex.

When to Use Each Traversal

Inorder:

  • BST: get sorted order
  • Check if tree is BST
  • Flatten BST to sorted list

Preorder:

  • Copy tree
  • Serialize tree (save to file)
  • Prefix expression evaluation
  • Check if trees are identical

Postorder:

  • Delete tree (delete children first)
  • Evaluate expression trees
  • Calculate tree properties (height, size)

Level-order:

  • Print tree by levels
  • Find shortest path
  • Check completeness
  • Serialize for reconstruction

Example: Serialize and Deserialize

Preorder for serialization.

def serialize(root):
    if root is None:
        return "None,"
    return str(root.value) + "," + serialize(root.left) + serialize(root.right)

def deserialize(data):
    def helper(values):
        val = next(values)
        if val == "None":
            return None
        node = TreeNode(int(val))
        node.left = helper(values)
        node.right = helper(values)
        return node
    
    values = iter(data.split(','))
    return helper(values)

tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.right.left = TreeNode(4)

serialized = serialize(tree)
print(serialized)  # "1,2,None,None,3,4,None,None,None,"

restored = deserialize(serialized)

Preorder serialization: root, left, right. Deserialization follows same order.

Example: Check if Identical Trees

def is_identical(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.value != q.value:
        return False
    
    return is_identical(p.left, q.left) and is_identical(p.right, q.right)

Preorder traversal. Check root, then recursively check left and right.

The Pattern

Tree traversals are about order:

  • Recursive: Elegant, uses call stack
  • Iterative: Explicit stack, more control
  • Morris: O(1) space, complex

Understanding traversals means understanding when to process root relative to children. That choice determines the output order and what problems you can solve.

Master traversals, and you'll handle trees like a pro.