Binary tree — structure, traversals - preorder, inorder, postorder (recursive and iterative)

WHAT is a binary tree?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None   # left subtree (a Node or None)
        self.right = None  # right subtree

WHY two children? "Binary" = base-2 branching. This restriction is what lets us reason cleanly: at every node there are exactly two recursive sub-problems (left subtree, right subtree), each itself a binary tree. This self-similarity is why recursion fits trees like a glove.

The ONE idea behind all three traversals

A traversal visits every node exactly once. For each node you do 3 jobs:

1. N — process (visit) the current Node.
2. L — recurse into the Left subtree.
3. R — recurse into the Right subtree.

L always comes before R. The only difference is where N sits:

Recursive traversals (derive from first principles)

The recursion is the definition. "To traverse a tree = visit root + traverse left + traverse right", reorder the three lines:

def preorder(node, out):
    if node is None: return        # base case: empty tree → nothing
    out.append(node.val)           # N
    preorder(node.left, out)       # L
    preorder(node.right, out)      # R
 
def inorder(node, out):
    if node is None: return
    inorder(node.left, out)        # L
    out.append(node.val)           # N
    inorder(node.right, out)       # R
 
def postorder(node, out):
    if node is None: return
    postorder(node.left, out)      # L
    postorder(node.right, out)     # R
    out.append(node.val)           # N

Why the if node is None: return? It is the empty tree base case. Without it the recursion never stops and you crash on None.left.

Iterative traversals (the WHY: recursion = a stack)

Iterative Preorder

Idea: pop a node, visit it, push right first then left (so left pops first — we want N L R).

def preorder_iter(root):
    if root is None: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)          # N — visit on pop
        if node.right: stack.append(node.right)  # push R first…
        if node.left:  stack.append(node.left)   # …so L pops first
    return out

Why push right before left? Stack reverses order. To process left before right we must push left last (on top).

Iterative Inorder

Idea: go as far left as possible pushing nodes, then pop (visit), then turn right.

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                # 1) dive left, stacking ancestors
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()         # 2) leftmost unvisited node
        out.append(cur.val)       # N — visit between L and R
        cur = cur.right           # 3) now handle its right subtree
    return out

Why dive left first? Inorder needs the left subtree fully done before the node, so we stash ancestors and only visit on the way back up.

Iterative Postorder (two-stack trick — easiest to remember)

Idea: Postorder is reverse of "Root Right Left". Do a preorder-like pass but push left before right, collect into a second stack, then reverse.

def postorder_iter(root):
    if root is None: return []
    s1, s2 = [root], []
    while s1:
        node = s1.pop()
        s2.append(node.val)         # building Root,Right,Left order
        if node.left:  s1.append(node.left)
        if node.right: s1.append(node.right)
    return s2[::-1]                 # reverse → Left,Right,Root = postorder

Why does reversing work? N R L reversed is L R N, which is exactly postorder. Slick.

Complexity (derive it)

• Time = $O(n)$ for all traversals: each of the $n$ nodes is visited (pushed/popped) a constant number of times.
• Space = $O(h)$ where $h$ = tree height (the stack/recursion depth).
  • Balanced tree: $h \approx \log_2 n$ → $O(\log n)$.
  • Skewed (linked-list-like) tree: $h = n$ → $O(n)$.

Why $O(h)$ not $O(n)$ space? At any moment the stack holds only the chain of ancestors from root to the current node — at most one per level.

Flashcards

Connections

• Binary Search Tree — inorder gives sorted order here.
• Recursion and the Call Stack — explains why DFS ⇔ stack.
• Stack (LIFO) — the engine of iterative traversals.
• Tree Height and Balance — drives the $O(h)$ space.
• Level-order Traversal (BFS) — the queue-based cousin of these DFS orders.
• Construct Tree from Preorder + Inorder — application of traversal uniqueness.

Concept Map

Hinglish (regional understanding)