Tree Traversals

Four orders

Visiting every node in a tree is not one algorithm — it is four, differing only in when you handle a node relative to its children.

Assume the node type from Trees:

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

Three of the four are the same recursion with one line moved:

static void preOrder(TreeNode node) {
    if (node == null) return;
    System.out.println(node.value);    // handle first
    preOrder(node.left);
    preOrder(node.right);
}

static void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.println(node.value);    // handle in the middle
    inOrder(node.right);
}

static void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.value);    // handle last
}

That is the whole difference. Where the visit sits decides the order.

What each is for

Choosing a traversal

Two of these are worth dwelling on.

In-order on a search tree gives sorted output. Because everything left is smaller and everything right is larger, visiting left-then-node-then-right produces ascending order. That is a good way to verify a search tree is correctly built.

Post-order is what you need when a node’s answer depends on its children. Computing a subtree’s size or height requires the children’s answers first:

static int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);       // children first
    int right = height(node.right);
    return 1 + Math.max(left, right);   // then this node
}

Deleting a tree is the same reason in reverse — free the children before the parent, or you lose the references to them.

Level-order

The odd one out. It cannot be done with plain recursion because it moves across the tree rather than down it. Use a queue:

static void levelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);

        if (node.left != null)  queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

This is breadth-first search applied to a tree.

To process one level at a time — printing each row on its own line, say — capture the queue size before draining that level:

while (!queue.isEmpty()) {
    int levelSize = queue.size();       // fixed before we add the next level

    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        if (node.left != null)  queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    System.out.println();               // end of this level
}

Reading queue.size() into a variable first is essential. Using queue.size() directly in the loop condition would include nodes added during the loop, and the levels would run together.

Iterative versions

Recursion is clearer, but a very deep tree can overflow the call stack. An explicit stack removes that limit.

Pre-order is the easy one:

static void preOrderIterative(TreeNode root) {
    if (root == null) return;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.value);

        if (node.right != null) stack.push(node.right);   // right first...
        if (node.left != null)  stack.push(node.left);    // ...so left pops first
    }
}

Pushing right before left is deliberate. A stack reverses order, so the last pushed is processed first — pushing left last means left is handled first, matching pre-order.

In-order iteratively is trickier, because you must descend fully left before handling anything:

static void inOrderIterative(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {       // go as far left as possible
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();          // handle the deepest unvisited
        System.out.println(current.value);
        current = current.right;        // then move right
    }
}

The loop condition needs both parts. current != null covers descending; !stack.isEmpty() covers coming back up.

Traversal for non-binary trees

Not every tree has exactly two children. With a list of children, the same shapes apply:

class Node {
    int value;
    List<Node> children = new ArrayList<>();
}

static void preOrder(Node node) {
    System.out.println(node.value);
    for (Node child : node.children) {
        preOrder(child);
    }
}

There is no meaningful in-order for more than two children — “the middle” is undefined. Pre-order, post-order, and level-order all still work.

Next

Related