4.3.2.1 - Tree traversals (Java)

Pre-order, in-order and post-order

A tree traversal visits every node, but changing when a node is processed changes the resulting sequence.

For a binary tree, apply the same rule to every subtree, including one with a single node. An empty subtree produces no visit. Here “visit” means process/output the node's value, not merely arrive at the node while navigating.

[DIAGRAM: asset_slug: traversal_tree; description: Binary search tree rooted at 8, with left subtree rooted at 3 and right subtree rooted at 10, used for all three traversal sequences.]

The exact child links are 8:(3,10), 3:(1,6), 6:(4,7), 10:(empty,14), 14:(13,empty); nodes 1,4,7,13 are leaves. Applying the rules gives:

• Pre-order: 8, 3, 1, 6, 4, 7, 10, 14, 13.
• In-order: 1, 3, 4, 6, 7, 8, 10, 13, 14.
• Post-order: 1, 4, 7, 6, 3, 13, 14, 10, 8.

For example, the subtree at 6 gives 6,4,7 in pre-order; 4,6,7 in in-order; and 4,7,6 in post-order. Build a trace from these smaller subtrees instead of guessing a left-to-right sweep across the drawing.

Tracing recursive visits

Recursive Java traversal uses a null-node base case and suspends a call while its child subtree is processed.

Assume this nested class inside the containing class, and import java.util.*; for output lists:

static class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

static void inOrder(Node node, List<Integer> output) {
    if (node == null) return;
    inOrder(node.left, output);
    output.add(node.value);
    inOrder(node.right, output);
}

At 8, the call first descends to 3 and then 1. The null left child of 1 returns immediately; only then is 1 appended. The call on 1's null right child returns, and 3's suspended call resumes and appends 3. Calls create no output merely by entering or returning. For pre-order move the add before both child calls; for post-order move it after both. An empty tree leaves the output list empty.