Tree Traversals

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~30 minutes

Table of Contents

1. The Sample Tree
2. Depth-First Traversals: Inorder, Preorder, Postorder
3. Recursive Implementations
4. Iterative Implementations (Explicit Stack)
5. Breadth-First Traversal: Level-Order
6. Choosing a Traversal
7. Summary & Next Steps

1. The Sample Tree

Every traversal in this chapter is demonstrated against the same tree:

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

2. Depth-First Traversals: Inorder, Preorder, Postorder

All three visit every node, differing only in when the current node is visited relative to its children:

Notice inorder produces the values in sorted order on this tree — that's not a coincidence, it's the defining property of a binary search tree (Chapter 3).

3. Recursive Implementations

def inorder(node, result=None):
    if result is None:
        result = []
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result
 
def preorder(node, result=None):
    if result is None:
        result = []
    if node is not None:
        result.append(node.value)
        preorder(node.left, result)
        preorder(node.right, result)
    return result
 
def postorder(node, result=None):
    if result is None:
        result = []
    if node is not None:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.value)
    return result
    # All three: O(n) time (every node visited once), O(h) space (call stack, Chapter 1)

The three functions are identical except for where result.append(node.value) sits relative to the two recursive calls — a useful way to remember them: the traversal's name describes when the "node" step happens (in-order = in the middle, pre-order = before, post-order = after).

4. Iterative Implementations (Explicit Stack)

Recursion implicitly uses the call stack (Chapter 1). You can make that stack explicit using a Python list, exactly as Module 5 introduced for stack-based problems:

def preorder_iterative(root):
    if root is None:
        return []
    result = []
    stack = [root]              # Module 5's stack, used explicitly
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right is not None:    # push right FIRST so left is processed first (LIFO)
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return result
    # O(n) time, O(h) space — same complexity as the recursive version,
    # just with the stack made explicit instead of implicit

Iterative inorder is slightly trickier because you need to remember where you are in the descent:

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while stack or current is not None:
        while current is not None:      # walk all the way left, stacking as you go
            stack.append(current)
            current = current.left
        current = stack.pop()             # backtrack to the last unvisited node
        result.append(current.value)
        current = current.right            # then explore its right subtree
    return result
    # O(n) time, O(h) space

5. Breadth-First Traversal: Level-Order

Unlike the three DFS orders above, level-order visits nodes level by level, left to right — this requires a queue (Module 5), not a stack:

from collections import deque
 
def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])          # Module 5's queue — FIFO order
    while queue:
        node = queue.popleft()      # O(1) with deque, unlike list.pop(0)
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result
    # O(n) time, O(w) space, where w is the tree's maximum width (widest level)

On the sample tree: 4, 2, 6, 1, 3, 5, 7 — each row read left to right. This directly reuses Module 5 Chapter 3's point that collections.deque gives O(1) operations at both ends, which is exactly what a queue-based traversal needs.

6. Choosing a Traversal

7. Summary & Next Steps

Key Takeaways

• Inorder, preorder, and postorder differ only in when the current node is visited relative to its children — all three are O(n) time, O(h) space.
• Any recursive traversal can be rewritten iteratively using an explicit stack (Module 5) — same complexity, more visible mechanics.
• Level-order traversal is fundamentally different — it's breadth-first, uses a queue instead of a stack, and processes the tree row by row.
• Inorder traversal of a BST (Chapter 3) yields sorted output — this is not a coincidence, it follows directly from the BST ordering property.

Concept Check

1. What single change distinguishes the preorder, inorder, and postorder recursive functions from each other?
2. Why does level-order traversal require a queue instead of a stack?
3. Why does inorder traversal of a BST produce values in sorted order?

Next Chapter

→ Chapter 3: Binary Search Trees

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index