Traversals

Written Explanation

The idea: visit, then recurse

A traversal handles ("visits") every node exactly once. For each node there are three things to do: visit the node itself, traverse its left subtree, traverse its right subtree. The three recursive traversals differ only in where the visit goes. Left is always done before right.

"Visit" here means "add the value to a list". The methods below take a list to fill. We use the tree built by inserting 8, 3, 10, 1, 6, 14:

        8
       / \
      3   10
     / \    \
    1   6    14

static void preOrder(Node n, List<Integer> out) {
    if (n == null) return;
    out.add(n.value);              // visit first
    preOrder(n.left, out);
    preOrder(n.right, out);
}

static void inOrder(Node n, List<Integer> out) {
    if (n == null) return;
    inOrder(n.left, out);
    out.add(n.value);              // visit in the middle
    inOrder(n.right, out);
}

static void postOrder(Node n, List<Integer> out) {
    if (n == null) return;
    postOrder(n.left, out);
    postOrder(n.right, out);
    out.add(n.value);              // visit last
}

The three methods are identical except for the line out.add(...). The null check comes first in each, as always.

Tracing in-order by hand

For the tree above, inOrder(8) first runs inOrder(3). That runs inOrder(1), which has no children and adds 1. Back in 3: add 3, then inOrder(6) adds 6. Back in 8: add 8, then inOrder(10), which has no left child, adds 10, then goes right and adds 14. The result is 1, 3, 6, 8, 10, 14.

That list is sorted. It is not luck. By the BST rule, everything in a node's left subtree is smaller than the node, and everything in the right subtree is larger. In-order visits the whole left subtree, then the node, then the whole right subtree, so at every node the values come out in increasing order. If the tree is not a BST, the in-order output is still a valid traversal, but it is not sorted.

Level-order: row by row

Level-order visits the root, then all nodes one link below, then all nodes two links below, and so on, going left to right in each row. It cannot be written as a short recursion, because it jumps between subtrees. Instead it uses a queue, first in, first out, which you met in the collections module.

The idea: put the root in the queue. Repeatedly take the front node, visit it, and add its children to the back. Because children are added behind everything already waiting, a whole row is finished before the next row begins.

static List<Integer> levelOrder(Node root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node n = queue.poll();
        out.add(n.value);
        if (n.left != null) queue.offer(n.left);
        if (n.right != null) queue.offer(n.right);
    }
    return out;
}

Here the null checks are on the children, because a Queue created by ArrayDeque does not accept null elements. The empty tree is handled at the top. This traversal is also called breadth-first, because it goes across before it goes down. The three recursive ones are depth-first: they go all the way down one path first.

Cost

Every traversal visits each node once and does a constant amount of work per visit, so the cost is O(n) for a tree of n nodes, whatever the shape. Level-order also needs extra memory for the queue, at most the width of the widest row. The recursive versions use stack space equal to the tree's height, because each pending call is a frame on the call stack.