Lesson 16.2 · Binary Trees

Depth-First Traversals: Pre, In and Post Order

The three DFS orders differ only in when you visit the node: before its children, between them, or after them.

14 min

Think of it like this

Touring a house room by room: pre-order is writing each room's name as you enter it, post-order is writing it as you leave it (after all the rooms beyond it), and in-order is writing it between visiting the left wing and the right wing.

1.Three orders, one shape

Pre-order (node, left, right): copying a tree, serialising it, passing information down. In-order (left, node, right): on a binary search tree this visits values in sorted order. Post-order (left, right, node): computing something from the children first, like heights, sizes and deleting trees.

Orders.java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    TreeNode(int val) { this(val, null, null); }
}

public class Main {
    static void pre(TreeNode n, List<Integer> out)  { if (n == null) return; out.add(n.val); pre(n.left, out); pre(n.right, out); }
    static void in(TreeNode n, List<Integer> out)   { if (n == null) return; in(n.left, out); out.add(n.val); in(n.right, out); }
    static void post(TreeNode n, List<Integer> out) { if (n == null) return; post(n.left, out); post(n.right, out); out.add(n.val); }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>(), c = new ArrayList<>();
        pre(root, a); in(root, b); post(root, c);
        System.out.println("pre  " + a + "\nin   " + b + "\npost " + c);
    }
}

Output

pre  [4, 2, 1, 3, 6]
in   [1, 2, 3, 4, 6]
post [1, 3, 2, 6, 4]

2.Iterative DFS with a stack

Deep trees can overflow the call stack. Pre-order iteratively: push the root; pop a node, visit it, push its right child then its left child (so the left is processed first). In-order iteratively: go left as far as possible pushing nodes, pop and visit, then move to the right child.

▶ Dry run: Iterative in-order on [4, 2, 6, 1, 3]root = [4, 2, 6, 1, 3]

stack(stack)

421

visited(list)

empty

Step 1/4Go left from 4 as far as possible, pushing 4, 2, 1.

Remember

Pre: node first. In: node between. Post: node last.
In-order of a BST is sorted.
Use an explicit stack for very deep trees.

Common mistakes

Pushing the left child before the right in iterative pre-order (reverses the order).

Command Palette

Depth-First Traversals: Pre, In and Post Order

1.Three orders, one shape

2.Iterative DFS with a stack