---
title: "Tree Traversal"
description: "Preorder, inorder, and postorder — the same tree, three visiting orders."
source: https://vizlearn.app/algorithms/search/tree-traversal
---

# Tree Traversal

Tree traversal is visiting every node exactly once in a defined order. The three depth-first orders — **preorder**, **inorder**, and **postorder** — are the *same* recursive walk: down each left subtree, back up, down each right subtree. They differ in one thing only — *when* a node is recorded: before, between, or after the two recursive calls on its children, respectively.

Move that single visit and the whole output reorders, though the walk never changes. Traversal costs O(n) time and O(h) space, where h is the height of the tree.

That last clause about the walk is the part people miss. Watch someone learn this and they memorize three separate recipes — "root-left-right, left-root-right, left-right-root" — as if they were three different algorithms. They are not. There is one algorithm, and a single moveable line inside it. Once you see the walk as fixed and the *visit* as the only thing that slides, the three orders stop being trivia to cram and become one idea you can rebuild from scratch.

## One Walk, One Moveable Line

Here is the whole algorithm. `visit(node)` is whatever you do with a node — print it, collect it, sum it. Everything else is scaffolding.

```python
def traverse(node):
    if node is None:
        return
    # visit(node)  <- preorder puts it here
    traverse(node.left)
    # visit(node)  <- inorder puts it here
    traverse(node.right)
    # visit(node)  <- postorder puts it here
```

The two `traverse(...)` calls are the walk: always left first, then right, all the way down until a child is `None` and the base case returns. That descent-and-return pattern is identical in all three orders. The only decision is which of the three commented positions the real `visit(node)` line occupies. Preorder emits a node the instant it arrives, before descending. Inorder emits it in the gap between finishing the left subtree and starting the right. Postorder waits until both subtrees are completely done. Same walk, three moments.

Because the walk is recursive, there is a **call stack** underneath it that you cannot see in the code but absolutely must picture. Every `traverse(child)` call stacks a new frame on top of the parent's; the parent's frame sits there, paused, waiting for the child to finish and return. That paused-parent frame is the answer to the question that trips everyone up in inorder and postorder: *why does a parent get recorded after some of its children?* Because the recursive calls on the children run first, and the parent's frame is still on the stack, waiting its turn.

We label nodes with letters (A, B, C…) rather than numbers on purpose. Traversal works on *any* binary tree, and a numeric labelling would quietly imply a binary *search* tree — where inorder famously produces sorted output. That sorted-inorder fact is real but it is a property of BSTs, not of traversal; letters keep this lesson about the walk itself.

## Tree Traversal Step by Step

The default run is **preorder** over the **Lopsided** tree — the same seven-node tree from Tree Basics:

```
        A
      /   \
     B     C
    / \   /
   D   E F
      /
     G
```

So `A → B, C`; `B → D, E`; `C → F`; `E → G`. Preorder visits a node *before* its subtrees, so trace it by saying "record, then go left, then go right" at every node and letting the base case turn you around at each empty child.

1. **call A** — enter `traverse(A)`, one frame on the stack. **visit A** → output `A`. Now recurse left.
2. **call B** — `traverse(A.left)` stacks `traverse(B)` (2 frames). **visit B** → output `A B`. Recurse left.
3. **call D** — `traverse(B.left)` stacks `traverse(D)` (3 frames). **visit D** → output `A B D`. D has no children: recursing left hits `None` and returns at once, and so does right. **return D** — D's frame pops; back in B.
4. **call E** — B's left is done, so B recurses right: `traverse(E)` (3 frames again). **visit E** → output `A B D E`. Recurse left.
5. **call G** — `traverse(E.left)` stacks `traverse(G)` (4 node frames — the deepest the stack panel gets on this tree). **visit G** → output `A B D E G`. G is a leaf: both child calls return immediately. **return G**, then **return E**, then **return B** — three frames pop in a row as each finishes, and we are back in A.
6. **call C** — A's left subtree is finished, so A recurses right: `traverse(C)` (2 frames). **visit C** → output `A B D E G C`. Recurse left.
7. **call F** — `traverse(C.left)` stacks `traverse(F)` (3 frames). **visit F** → output `A B D E G C F`. F is a leaf; it returns, then C returns, then A returns. The stack drains to empty and the walk is done.

Preorder over this tree is **A B D E G C F**. Notice two things the animation makes vivid. First, the root A came out *first* — that is preorder's signature. Second, the call stack peaked at **four node frames** (A, B, E, G) — exactly the tree's height (3) plus one. The panel counts only calls on real nodes: a base-case call on an empty child adds one more frame for an instant, then returns before doing anything. The stack is never deeper than the longest path you are currently descending.

## The Same Walk, a Different Moment

Keep the identical tree and identical descent. Slide the `visit` line and read the two other orders straight off the same walk:

- **Inorder** (visit *between* the two calls): `D B G E A F C`. Each node waits for its whole left subtree, records itself, then does its right. The root A lands between the left-subtree output and the right-subtree output.
- **Postorder** (visit *after* both calls): `D G E B F C A`. A node is recorded only once both its subtrees are completely finished, so every parent trails its children — and the root A comes out dead **last**.

Line them up:

| Order | Visit position | Output |
|---|---|---|
| Preorder | before both calls | `A B D E G C F` |
| Inorder | between the calls | `D B G E A F C` |
| Postorder | after both calls | `D G E B F C A` |

Same seven `call`/`return` events in the same sequence for all three. The only difference is where each node's letter falls in the stream — and that is decided entirely by the one line you moved.

Each order earns its keep on a real task. **Preorder** copies or serializes a tree top-down (you need a node before its children to rebuild it). **Inorder** on a binary *search* tree yields its keys in sorted order. **Postorder** frees or evaluates bottom-up — deleting a tree, or computing a value from an expression tree, where you need both operands before you can apply the operator.

## Why the Stack Depth Matters

| Case | Time | Space |
|---|---|---|
| Balanced tree | O(n) | O(log n) |
| Skewed tree (vine) | O(n) | O(n) |

Traversal touches each node a constant number of times, so its time complexity is O(n), flat. The subtler cost is *space*: the recursion holds one stack frame per pending call, and the stack is as deep as the path it is currently descending. On a balanced tree the deepest path is about log₂ n, so the stack stays shallow. On the **Skewed** preset — a one-child "vine" — every node stacks on the last, and the stack reaches depth **n**. Try it: the panel's stack tower climbs to all seven frames.

That is the breaking point. Space is O(h), and h ranges from log n (balanced) to n (a vine). A deep enough skewed tree overflows the call stack entirely — a real crash, not a slowdown. It is one more reason self-balancing trees exist, and the reason production code that must handle adversarial input often traverses with an explicit stack (or the pointer-only Morris traversal) instead of recursion.

## Edge Cases

- **Empty tree** — `traverse(None)` hits the base case immediately and returns. The output is empty, no matter the order.
- **Single node** — the root is a leaf: `call → visit → return`, one node frame on the stack (each empty child's base-case call adds one more for an instant), output is just that node. All three orders agree here.
- **A node with one child** — the missing side is still visited: `traverse` is called on the `None` child, the base case returns at once, and the walk moves on. That is why the Lopsided tree's C (left child only) and E (left child only) still produce correct output — the empty right subtree costs one instant base-case return, not a skipped step.
- **A leaf** — both child calls return immediately, so a leaf is `call → visit → return` with nothing in between. Leaves are where the recursion turns around.
- **A degenerate (skewed) tree** — correct in every order, but the call stack reaches depth n. For a large enough vine this overflows the stack; use an iterative traversal instead.

## Common Mistakes

- **Treating the three orders as three algorithms.** They share one walk. If you memorize `root-left-right`, `left-root-right`, `left-right-root` as unrelated strings, you will mix them up under pressure. Remember instead: the walk is fixed; only the `visit` line slides.
- **Expecting the root first in inorder or postorder.** The root is emitted first *only* in preorder. In inorder it lands between its left and right subtrees; in postorder it is last, because its subtrees must finish before it is recorded.
- **Forgetting the base case.** `if node is None: return` is what stops the recursion at empty children. Drop it and `traverse(node.left)` on a leaf recurses into `None`, dereferences a missing node, and crashes. Null children get no visit — they simply return.
- **Assuming inorder means "sorted."** Inorder yields sorted output only on a binary *search* tree, where the ordering invariant holds. On an arbitrary binary tree — like this one, labelled with letters — inorder is just `D B G E A F C`, no sorting implied.
- **Ignoring the stack on deep trees.** Recursion's O(h) space is invisible until a skewed tree makes h = n and the stack overflows. For untrusted or pathological input, reach for an explicit stack or an iterative traversal.