TreesLesson 3

Tree Traversals — DFS

Inorder, preorder, and postorder traversal — three ways to visit every node using depth-first search, both recursive and iterative.

What Is It?

Traversal means visiting every node in the tree exactly once. Depth-first search (DFS) means you go as deep as possible down one branch before coming back and exploring another.

There are three DFS orderings. The difference is just: when do you process the current node relative to its children?

Inorder: left subtree, then current node, then right subtree
Preorder: current node first, then left subtree, then right subtree
Postorder: left subtree, then right subtree, then current node last

All three visit every node. They just visit them in a different order. Each order has a specific use case:

Inorder on a BST gives you sorted values
Preorder is useful for copying or printing a tree
Postorder is useful when children need to be processed before their parent (like deleting a tree)

Analogy

Reading a Book

Imagine a book organized as a tree: the book is the root, chapters are its children, and each chapter has sections.

Preorder is like reading the table of contents top-down. You write down the book title first, then the chapter title, then each section under it, then the next chapter. Parent before children.

Inorder is the natural left-to-right reading order. For a BST, this gives you values in sorted order.

Postorder is like cleaning up your office. You clear the small drawers first, then the desk they sit on, then the whole room. Children before parent. This is how you'd safely delete a tree — you must remove children before removing the parent that points to them.

How It Works

The Example Tree

We'll trace all three traversals on this tree:

pseudocode

INORDER (Left, Node, Right)

pseudocode

function inorder(node):
    if node is null:
        return
    inorder(node.left)
    process(node)          // Visit the node
    inorder(node.right)

Trace — follow each call and watch the output build:

pseudocode

inorder(1)
  inorder(2)
    inorder(4)
      inorder(null) -> return
      PROCESS 4                  output: 4
      inorder(null) -> return
    PROCESS 2                    output: 4, 2
    inorder(5)
      inorder(7)
        inorder(null) -> return
        PROCESS 7                output: 4, 2, 7
        inorder(null) -> return
      PROCESS 5                  output: 4, 2, 7, 5
      inorder(null) -> return
  PROCESS 1                      output: 4, 2, 7, 5, 1
  inorder(3)
    inorder(null) -> return
    PROCESS 3                    output: 4, 2, 7, 5, 1, 3
    inorder(6)
      inorder(null) -> return
      PROCESS 6                  output: 4, 2, 7, 5, 1, 3, 6
      inorder(null) -> return
INORDER result: 4, 2, 7, 5, 1, 3, 6

PREORDER (Node, Left, Right)

pseudocode

function preorder(node):
    if node is null:
        return
    process(node)          // Visit FIRST
    preorder(node.left)
    preorder(node.right)

Trace:

pseudocode

preorder(1)
  PROCESS 1                      output: 1
  preorder(2)
    PROCESS 2                    output: 1, 2
    preorder(4)
      PROCESS 4                  output: 1, 2, 4
      preorder(null) -> return
      preorder(null) -> return
    preorder(5)
      PROCESS 5                  output: 1, 2, 4, 5
      preorder(7)
        PROCESS 7                output: 1, 2, 4, 5, 7
      preorder(null) -> return
  preorder(3)
    PROCESS 3                    output: 1, 2, 4, 5, 7, 3
    preorder(null) -> return
    preorder(6)
      PROCESS 6                  output: 1, 2, 4, 5, 7, 3, 6
PREORDER result: 1, 2, 4, 5, 7, 3, 6

Notice the root (1) is always first in preorder. That's what makes it great for serializing a tree — when you reconstruct it, the first value you read is the root.

POSTORDER (Left, Right, Node)

pseudocode

function postorder(node):
    if node is null:
        return
    postorder(node.left)
    postorder(node.right)
    process(node)          // Visit LAST

Trace:

pseudocode

postorder(1)
  postorder(2)
    postorder(4)
      postorder(null) -> return
      postorder(null) -> return
      PROCESS 4                  output: 4
    postorder(5)
      postorder(7)
        PROCESS 7                output: 4, 7
      postorder(null) -> return
      PROCESS 5                  output: 4, 7, 5
    PROCESS 2                    output: 4, 7, 5, 2
  postorder(3)
    postorder(null) -> return
    postorder(6)
      PROCESS 6                  output: 4, 7, 5, 2, 6
    PROCESS 3                    output: 4, 7, 5, 2, 6, 3
  PROCESS 1                      output: 4, 7, 5, 2, 6, 3, 1
POSTORDER result: 4, 7, 5, 2, 6, 3, 1

Notice the root (1) is always last. Leaves come before their parents — perfect for deletion or computing something that depends on children's results.

All Three Side by Side

pseudocode

         1
        / \
       2   3
      / \   \
     4   5   6
        /
       7
INORDER:   4, 2, 7, 5, 1, 3, 6   (left, NODE, right)
PREORDER:  1, 2, 4, 5, 7, 3, 6   (NODE, left, right)
POSTORDER: 4, 7, 5, 2, 6, 3, 1   (left, right, NODE)

Iterative Inorder Using a Stack

The recursive versions use the call stack automatically. For iterative inorder (commonly asked in interviews), you manage your own stack:

pseudocode

function inorderIterative(root):
    stack = []
    current = root
    result = []
    
    while current is not null OR stack is not empty:
        // Go as far left as possible
        while current is not null:
            stack.push(current)
            current = current.left
        
        // Process the top of stack
        current = stack.pop()
        result.append(current.data)
        
        // Move to right subtree
        current = current.right
    
    return result

The key idea: "go left as far as you can, then pop and process, then go right."

Step-by-step trace:

pseudocode

Step  | Action              | Stack          | Output
──────|─────────────────────|────────────────|───────
  1   | Push 1, go left     | [1]            |
  2   | Push 2, go left     | [1,2]          |
  3   | Push 4, go left     | [1,2,4]        |
  4   | null, pop 4         | [1,2]          | 4
  5   | right=null          |                |
  6   | Pop 2               | [1]            | 4,2
  7   | right=5, push 5     | [1,5]          |
  8   | Push 7, go left     | [1,5,7]        |
  9   | null, pop 7         | [1,5]          | 4,2,7
 10   | right=null          |                |
 11   | Pop 5               | [1]            | 4,2,7,5
 12   | right=null          |                |
 13   | Pop 1               | []             | 4,2,7,5,1
 14   | right=3, push 3     | [3]            |
 15   | left=null           |                |
 16   | Pop 3               | []             | 4,2,7,5,1,3
 17   | right=6, push 6     | [6]            |
 18   | left=null           |                |
 19   | Pop 6               | []             | 4,2,7,5,1,3,6
 20   | done                |                |

When to Use Each Traversal

Inorder (L-Root-R)

Get sorted order from BST
Flatten BST to sorted array
Validate BST property

sorted order from BST

Preorder (Root-L-R)

Copy/clone a tree
Serialize a tree
Prefix expression evaluation
Print tree with indentation

root comes first

Postorder (L-R-Root)

Delete/free a tree safely
Calculate directory sizes
Postfix expression evaluation
Parent depends on children

children before parent

Time and Space

All three traversals:

Time: O(n) — every node is visited exactly once
Space: O(h) — the recursion depth equals the tree's height. O(log n) for a balanced tree, O(n) worst case.

Examples

Example 1: Inorder on a BST gives sorted output

pseudocode

        8
       / \
      3   10
     / \    \
    1   6   14
Inorder: 1, 3, 6, 8, 10, 14  -- sorted!

Example 2: Preorder for serialization

pseudocode

      1
     / \
    2   3
Preorder (including nulls): 1, 2, null, null, 3, null, null
To reconstruct: first value (1) is the root.
Next is 2 = left child of 1.
Two nulls = 2 has no children.
Next is 3 = right child of 1.
Two nulls = 3 has no children.

Example 3: Postorder for computing subtree sums

pseudocode

      1
     / \
    2   3
   / \
  4   5
Postorder visits: 4, 5, 2, 3, 1
Subtree sums computed bottom-up:
  Node 4: sum = 4
  Node 5: sum = 5
  Node 2: sum = 2 + 4 + 5 = 11
  Node 3: sum = 3
  Node 1: sum = 1 + 11 + 3 = 15

Postorder is natural here — you need children's answers before the parent's.

Common Mistakes

Mixing up the three orders. Use the name as a hint: IN-order = node is IN the middle (left, node, right). PRE-order = node is FIRST (node, left, right). POST-order = node is LAST (left, right, node).

Forgetting the null check. Every recursive tree function must start with if node is null: return. Without it, you'll crash on null children.

Thinking inorder always gives sorted output. That's only true for a BST. For a random binary tree, inorder is just left-to-right and has no sorting guarantee.

Getting iterative inorder wrong. The right child doesn't get pushed onto the stack directly — it becomes the new current so the inner while loop can push all of its left children.

Best Practices

Start with the recursive version — it's cleaner and matches the problem structure. Switch to iterative only if you need to
Use the mnemonic: Inorder = In-between, Preorder = Pre-first, Postorder = Post-last
Ask yourself: does a node's answer depend on its children's answers? If yes, use postorder. Need top-down? Use preorder. Need sorted BST output? Use inorder
Practice the iterative inorder pattern until it feels automatic — it shows up often in interviews

Binary Search Trees Tree Traversals — BFS