Coding Patterns
Tree Traversal

Tree Traversal

Tree Traversal is the foundation of solving tree-based problems. Whether you are validating a BST, finding a path sum, or serializing a tree, understanding traversal orders is essential. This pattern enables you to visit every node in a tree exactly once in a specific order.

Real-World Analogy

Think of a tree traversal like exploring a family tree:

  • Inorder (Left, Root, Right): Like reading a book from left to right: visit all ancestors on the left, then the current person, then all on the right.
  • Preorder (Root, Left, Right): Like introducing yourself first at a party, then introducing everyone on your left, then your right.
  • Postorder (Left, Right, Root): Like calculating folder sizes: you need to know the sizes of subfolders before the parent.
  • Level Order (BFS): Like taking a group photo by rows: first row stands, then second row, and so on.

Visual Explanation

Let us visualize the four main traversal orders on a sample binary tree:

  flowchart TD
    subgraph Tree["Binary Tree"]
        A((1))
        B((2))
        C((3))
        D((4))
        E((5))
        F((6))
        G((7))

        A --> B
        A --> C
        B --> D
        B --> E
        C --> F
        C --> G
    end

Traversal Results:

  • Inorder (Left, Root, Right): 4, 2, 5, 1, 6, 3, 7
  • Preorder (Root, Left, Right): 1, 2, 4, 5, 3, 6, 7
  • Postorder (Left, Right, Root): 4, 5, 2, 6, 7, 3, 1
  • Level Order (BFS): [[1], [2, 3], [4, 5, 6, 7]]

Depth-First vs Breadth-First 

  flowchart LR
    subgraph DFS["Depth-First (Stack/Recursion)"]
        D1[Go deep first]
        D2[Backtrack when stuck]
        D3[Inorder/Preorder/Postorder]
        D1 --> D2 --> D3
    end

    subgraph BFS["Breadth-First (Queue)"]
        B1[Process level by level]
        B2[Use queue for ordering]
        B3[Level Order Traversal]
        B1 --> B2 --> B3
    end

When to Use This Pattern

Use tree traversal when you encounter:

  • Need to visit all nodes in a binary tree or n-ary tree
  • BST validation: inorder traversal should produce sorted values
  • Path finding: track nodes from root to leaf
  • Tree serialization and deserialization
  • Calculate metrics like height, depth, or diameter
  • Clone or copy a tree structure
  • Expression tree evaluation

Complexity Analysis

Traversal TypeTime ComplexitySpace ComplexityNotes
Recursive DFS
O(N)
O(H)
H = tree height. Worst case O(N) for skewed tree
Iterative DFS
O(N)
O(H)
Explicit stack avoids recursion limits
BFS (Level Order)
O(N)
O(W)
W = max width. For complete tree, W = N/2

Derivation:

  • Time: Each node is visited exactly once, giving
    O(N)
    .
  • Space (DFS): The call stack or explicit stack holds at most H nodes at a time, where H is the tree height.
  • Space (BFS): The queue holds at most one level at a time. In the worst case (complete tree), the last level has N/2 nodes.

Common Mistakes

  1. Forgetting null checks: Always check if a node is null before accessing its properties.
  2. Wrong traversal order: Mixing up inorder, preorder, and postorder can produce incorrect results.
  3. Using recursion for deep trees: Very deep trees can cause stack overflow. Consider iterative solutions.
  4. Stack vs Queue confusion: DFS uses stack (LIFO), BFS uses queue (FIFO).
  5. Not handling single-node trees: Edge case where root has no children.

Next Steps

Ready to apply these concepts? Check out: