Tree Traversal

Three traversal orders over the same structure, each revealing a different meaning.

Context

A binary tree can be traversed in three canonical ways:

• Pre-order
• In-order
• Post-order

All three traversals walk the same tree and use nearly identical recursive code. The only difference is when the current node is processed relative to its children — and that small difference leads to very different outcomes.

• Pre-order: visit the current node first, then traverse the left subtree, followed by the right subtree.
• In-order: traverse the left subtree first, then visit the current node, and finally traverse the right subtree.
• Post-order: traverse the left subtree, then the right subtree, and visit the current node last.

Traversing the left subtree before the right one is a convention, not a requirement.

Core idea

• Tree traversal is naturally expressed using recursion.
• Reaching a null node means the traversal has reached the end of a branch and should return.
• The three traversal algorithms are structurally symmetric.
• The only difference is the position of the “visit” step relative to recursive calls.
• This ordering determines what the traversal means, not just how it looks.

Application

Pre-order traversal — structure first

Mental model: “I need to process a node before I care about its children.”

Typical uses:

• Serializing a tree (e.g. saving structure + values)
• Copying a tree
• Evaluating expressions written in prefix notation
• Walking a tree where parent context matters before children

Key insight: Pre-order preserves the construction order of the tree.

In-order traversal — sorted meaning

Mental model: “I want values in a meaningful order derived from structure.”

Typical uses:

• Binary Search Trees → produces sorted output
• Range queries
• Validating BST invariants

Key insight: In-order traversal is only special because of BST properties. On a generic binary tree, it’s just another ordering.

Post-order traversal — children first, cleanup last

Mental model: “I must fully process children before touching the parent.”

Typical uses:

• Deleting a tree
• Freeing memory
• Evaluating expression trees (postfix notation)
• Computing derived properties bottom-up (height, size, balance)

Key insight: Post-order is ideal when a node depends on results from its subtrees.

Pre-order builds, in-order orders, post-order resolves.

Implementation

public class BinaryNode<T> {
    private T value;
    private BinaryNode<T> left;
    private BinaryNode<T> right;
    
    // getters, setters, constructors omitted for brevity
}

public class PreOrderTraversal {
    public static <T> List<T> walk(BinaryNode<T> root) {
        return walk(root, new ArrayList<>());
    }
    
    private static <T> List<T> walk(BinaryNode<T> node, List<T> list) {
        if (node == null) return list;
        
        list.add(node.getValue());
        walk(node.getLeft(), list);
        walk(node.getRight(), list);

        return list;
    }
}

public class InOrderTraversal {
    public static <T> List<T> walk(BinaryNode<T> root) {
        return walk(root, new ArrayList<>());
    }
    
    private static <T> List<T> walk(BinaryNode<T> node, List<T> list) {
        if (node == null) return list;
        
        walk(node.getLeft(), list);
        list.add(node.getValue());
        walk(node.getRight(), list);
        
        return list;
    }    
}

public class PostOrderTraversal {
    public static <T> List<T> walk(BinaryNode<T> root) {
        return walk(root, new ArrayList<>());
    }
    
    private static <T> List<T> walk(BinaryNode<T> node, List<T> list) {
        if (node == null) return list;
        
        walk(node.getLeft(), list);
        walk(node.getRight(), list);
        list.add(node.getValue());
        
        return list;
    }
}