Traver

Structure

Traversal

Code

Example

Tree values in level order. Use null for an empty spot.

Current node Waiting on the call stack Visited Output position

Code

Call Stack

Output

Show Null CallsStep into empty children as well, as the real recursion does. Exam Flag TrickPuts a dot on each node. Write the node down when you trace past its dot.

Speed

At a glance

Order	Rule	Root is	Outline dot	Uses
Pre-order	N → L → R	First	Left side	Recursion (stack)
In-order	L → N → R	Splits left from right	Underneath	Recursion (stack)
Post-order	L → R → N	Last	Right side	Recursion (stack)
Level-order	Row by row, left to right	First	None	Queue (BFS)

The name tells you where the Node goes: pre = before its children, in = between them, post = after them. Left always comes before right.

One tree, four orders

Pre-orderF B A D C E G I HRoot first

In-orderA B C D E F G H IRoot splits left subtree | right subtree

Post-orderA C E D B H I G FRoot last

Level-orderF B G A D I C E HRow by row

The outline trick

1Complete the tree. Add an empty edge wherever a child is missing, so every node has exactly two. A tree with n nodes needs n + 1.
2Trace the outline. Start above the root and go anticlockwise, hugging every node and edge.
3Read it off. Write a node as you pass its left (pre), underside (in) or right (post).

Which traversal for which job?

Print a BST in sorted order	In
Copy or serialise a tree	Pre
Delete or free every node	Post
Evaluate an expression tree	Post
Height, size or sum of a tree	Post
Print prefix notation	Pre
Minimum depth or shortest path	Level
Print each level on its own line	Level
Print a linked list backwards	Post

Code you should be able to write

struct Node { int val; struct Node *left, *right; }; and #define MAX 100

One template, three orders: only the visit moves

void dfs(struct Node *node) {
    if (node == NULL)
        return;
    visit(node);   // pre-order goes here
    dfs(node->left);
    visit(node);   // in-order goes here
    dfs(node->right);
    visit(node);   // post-order goes here
}

def dfs(node):
    if node is None:
        return
    visit(node)   # pre-order goes here
    dfs(node.left)
    visit(node)   # in-order goes here
    dfs(node.right)
    visit(node)   # post-order goes here

In-order without recursion (explicit stack)

void inorder(struct Node *root) {
    struct Node *stack[MAX];
    int top = 0;
    struct Node *node = root;
    while (top > 0 || node != NULL) {
        while (node != NULL) {     // go as far left as possible
            stack[top++] = node;
            node = node->left;
        }
        node = stack[--top];
        visit(node);
        node = node->right;
    }
}

def inorder(root):
    stack, node = [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        visit(node)
        node = node.right

Level-order (queue)

void levelorder(struct Node *root) {
    if (root == NULL) return;
    struct Node *queue[MAX];
    int front = 0, back = 0;
    queue[back++] = root;
    while (front < back) {
        struct Node *node = queue[front++];
        visit(node);
        if (node->left)  queue[back++] = node->left;
        if (node->right) queue[back++] = node->right;
    }
}

def levelorder(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        visit(node)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

Pre-order without recursion

void preorder(struct Node *root) {
    if (root == NULL) return;
    struct Node *stack[MAX];
    int top = 0;
    stack[top++] = root;
    while (top > 0) {
        struct Node *node = stack[--top];
        visit(node);
        if (node->right) stack[top++] = node->right;  // right first,
        if (node->left)  stack[top++] = node->left;   // so left pops first
    }
}

def preorder(root):
    stack = [root]
    while stack:
        node = stack.pop()
        visit(node)
        if node.right: stack.append(node.right)  # right first,
        if node.left:  stack.append(node.left)   # so left pops first

Rebuild a tree from two orders

Pre + In, Post + In or Level + In gives exactly one tree. Pre + Post does not, unless every node has 0 or 2 children.

1Pre F B A D C E G I H, so the root is F.
2Split in-order at F: A B C D E | F | G H I.
3The left part’s first value in pre-order is B, so B is the left child. Split again: A | B | C D E.
4Repeat on every part until each one is a single node.

Complexity and counts

O(n)Time for all four orders. Each node is visited once. O(h)Space for recursion, where h is the height: log n when balanced, n when skewed. O(w)Space for level-order, where w is the widest level (up to about n/2). n + 1Null pointers in any binary tree with n nodes. 2n + 1Total calls made by a recursive traversal.

Linked lists

A singly linked list is a tree where every node has only a right child, next.

Head → tailPre-order, in-order and level-order Tail → headPost-order (recurse first, then print) O(n) stackRecursion on a long list can overflow. A loop needs only O(1).

Exam traps

A node with one child still gets an empty edge. Skipping it is the most common in-order mistake.
Reversed post-order is N → R → L, not pre-order.
In-order on a BST must come out sorted. If it doesn’t, recheck your answer.
Leaves appear in the same left-to-right order in pre, in and post. Use this to check your answer.
Swapping the queue in level-order for a stack gives a depth-first order.

About Traver

Code

Call Stack

Output

The outline trick

1Step 1: give every node two branches

Output

At a glance

One tree, four orders

The outline trick

Which traversal for which job?

Code you should be able to write

Rebuild a tree from two orders

Complexity and counts

Linked lists

Exam traps