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

We use one tiny tree for the entire walkthrough so your eyes can lock onto it:

        1
       / \
      2   3
     / \
    4   5

Here 1 is the root (the top box, no arrow pointing into it), 4 and 5 are leaves (boxes with no arrows going out), and each box holds a number we call its value. This is exactly the tree from the parent topic.

Step 1 — What "visiting" a node even means

WHAT. A traversal is a walk that touches every box exactly once and writes its number into an output list. "Visiting" a node = the single moment we append that node's number to the list. Nothing more.

WHY. Before we can argue about order, we must pin down the atomic action. Everything downstream is just "in what sequence do these append-moments happen?"

PICTURE. Look at the figure. The tree sits on the left; the growing output list sits on the right as a row of slots. The coral arrow marks the one box being visited right now, and its number drops into the next empty slot.

Step 2 — The walk is self-similar (why recursion fits)

WHAT. Notice that the left child of 1 is itself the root of a smaller tree (2,4,5), and the right child 3 is a one-box tree. Every subtree is the same kind of object as the whole tree.

WHY. This self-similarity is the reason recursion fits trees like a glove: "traverse the tree" is defined in terms of "traverse the left tree" and "traverse the right tree" — the same instruction applied to smaller inputs. The walk stops when a subtree is empty (the None box), which is our base case.

PICTURE. The figure shades three nested regions: the whole tree (lavender), the left subtree rooted at 2 (mint), and the empty None children hanging off the leaves (dashed) — these dashed empties are where the walk turns around.

Step 3 — The call stack is a real stack of sticky notes

WHAT. When you dive from 1 into 2, you must remember that you still owe 1 its right child 3. That memory is a note: "come back to 1." Diving deeper stacks more notes. Coming back pops the top note.

WHY. Each recursive call secretly pushes a frame onto the call stack. A stack is LIFO — Last In, First Out — the note you wrote most recently is the one you handle first. That is exactly "go deep, then unwind the deepest thing first."

PICTURE. The figure follows the walk down the left spine 1 → 2 → 4. On the right, a vertical stack of notes grows upward: bottom note "1", then "2", then "4" on top. The top note is highlighted — it is always what we act on next.

Step 4 — Preorder: visit the instant you arrive (N L R)

WHAT. Choose to place N first: the moment you step onto a box, write its number, then dive left, then right. This gives preorder.

WHY. Placing N before both children means the parent is always recorded ahead of everything beneath it. This is what you want for copying a tree top-down or printing a directory before its contents.

PICTURE. The figure numbers the visit-moments in walk order. We touch 1 (write 1), dive to 2 (write 2), dive to 4 (write 4), back up, over to 5 (write 5), back up to 1, over to 3 (write 3).

$\text{preorder}=\underset{N}{\underbrace{1}}\underset{\text{left subtree}}{\underbrace{245}}\underset{\text{right subtree}}{\underbrace{3}}=12453$

• $\underset{N}{\underbrace{1}}$ :: the root, written first because N comes before L and R.
• $\underset{\text{left}}{\underbrace{245}}$ :: the entire left subtree, itself in preorder (2 first, then its kids).
• $\underset{\text{right}}{\underbrace{3}}$ :: the right subtree, done last.

The iterative version makes the stack explicit. Pop a node, visit it, then push right first, then left — because the stack reverses order, and we want left to pop first:

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 is on top, pops first

Step 5 — Inorder: visit between the children (L N R)

WHAT. Now slide N into the middle: fully finish the left subtree, then write the node, then do the right subtree.

WHY. The node is recorded only after everything to its left is done, so it lands "in the middle." For a Binary Search Tree this middle-placement is exactly what makes the output come out sorted — but note that sorted-ness is a property of the BST ordering, not of inorder on an arbitrary tree.

PICTURE. The figure shows the "dive to the leftmost box before writing anything" motion. We plunge 1 → 2 → 4, and only at the dead end do we start writing: 4, then back up to 2, then over to 5, then up to 1, then over to 3.

$\text{inorder}=\underset{\text{left subtree, L}}{\underbrace{425}}\underset{N}{\underbrace{1}}\underset{\text{right, R}}{\underbrace{3}}=42513$

• $\underset{\text{left}}{\underbrace{425}}$ :: the whole left subtree written before the root — done inorder itself (4 before 2 before 5).
• $\underset{N}{\underbrace{1}}$ :: the root, appearing between its two subtrees.
• $\underset{\text{right}}{\underbrace{3}}$ :: the right subtree, last.

The iterative version stashes ancestors while diving left, then visits on the way back up:

cur, stack = root, []
while cur or stack:
    while cur:                # 1) dive left, stacking every ancestor
        stack.append(cur)
        cur = cur.left
    cur = stack.pop()         # 2) deepest unvisited node
    out.append(cur.val)       # N — visited between L and R
    cur = cur.right           # 3) now go handle its right subtree

Step 6 — Postorder: visit last (L R N), via the reverse trick

WHAT. Push N to the very end: both children's subtrees finish completely, then write the node.

WHY. The parent is written only after every descendant, which is perfect for deleting/freeing a tree (free the children before the parent) or evaluating an expression tree bottom-up.

PICTURE. The figure shows children-before-parent: 4, then 5, then their parent 2; then 3; then finally the root 1 — dead last.

$\text{postorder}=\underset{\text{under }2}{\underbrace{45}}\underbrace{2}\underbrace{3}\underset{N\text{ last}}{\underbrace{1}}=45231$

• $\underbrace{45}$ :: left subtree's children, both before their parent.
• $2$ :: parent of 4 and 5, after both.
• $3$ :: right subtree.
• $\underset{N}{\underbrace{1}}$ :: the root, written absolutely last — after all descendants.

The slick iterative trick. Postorder is $LRN$. Reverse it and you get $NRL$ — a preorder-like walk that just swaps the push order (left before right). So: run that easy walk into a second stack, then reverse it.

s1, s2 = [root], []
while s1:
    node = s1.pop()
    s2.append(node.val)           # builds N R L order
    if node.left:  s1.append(node.left)
    if node.right: s1.append(node.right)
result = s2[::-1]                 # reverse → L R N = postorder

Step 7 — Edge and degenerate cases (never hit an unshown scenario)

WHAT. Two shapes break naive intuition: the empty tree and the skewed tree (every node has only one child — a disguised linked list).

WHY. These decide correctness and cost. The empty tree is the base case that stops recursion; the skewed tree is the worst case for stack depth, i.e. tree height.

PICTURE. Left panel: the empty tree — a single dashed None box; the walk writes nothing and returns immediately. Middle: a skewed tree 1 → 2 → 3 → 4 down the right; the stack grows to full depth $n$. Right: a balanced tree where depth is only about ${\log }_{2}n$.

$\text{Time}=O(n),\text{Space}=O(h)$

• $n$ :: number of nodes; every node is pushed/popped a constant number of times → linear time.
• $h$ :: height — the longest root-to-leaf chain, which is the deepest the stack ever gets.
• Balanced ⇒ $h\approx {\log }_{2}n$ ⇒ space $O(\log n)$. Skewed ⇒ $h=n$ ⇒ space $O(n)$.

Contrast this depth-first family with level-order (BFS), which uses a queue (FIFO) instead of a stack and visits row by row — a different tool for a different question. And notice that inorder + preorder together are enough to rebuild the whole tree, because preorder hands you the root and inorder splits left from right.

The one-picture summary

WHAT. One figure, the same tree three times, with the visit-order numbered under each node for pre/in/post — so you can read off all three outputs at a glance and see that the only thing that moved was the position of N.

PICTURE.