Traversing the Tree

size and height already visit every node, but only to combine the nodes into a single number. Often we want to visit each node and do something with the node itself: print its value, or copy it into a list. Visiting every node of a tree exactly once is called a traversal.

At any node there are three pieces of work to do: visit the node itself, traverse its left subtree, and traverse its right subtree. The two subtree traversals are recursive, exactly as in size and height. The only decision left is when to visit the node relative to those two recursive calls. There are three choices:

• visit the node before its subtrees,
• visit it between the two subtrees, or
• visit it after its subtrees.

The three choices give three traversals, called pre-order, in-order, and post-order. The name says where the visit happens. In code, the only difference is the position of one line.

We will run all three on this small tree:

       ╭───╮
       │ 3 │
       ╰─┬─╯
    ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮
  │ 5 │     │ 8 │
  ╰─┬─╯     ╰───╯
  ┌─┘
╭─┴─╮
│ 1 │
╰───╯

Start with pre-order:

public static <T> void preOrder(Node<T> node) {
  if (node == null) {
    return;  // base case: an empty tree has nothing to visit
  }
  System.out.println(node.value);  // visit
  preOrder(node.left);
  preOrder(node.right);
}

On our tree, it prints each node as soon as it reaches it:

3   5   1   8

Now move the visit line down, between the two recursive calls, and we have in-order:

public static <T> void inOrder(Node<T> node) {
  if (node == null) {
    return;
  }
  inOrder(node.left);
  System.out.println(node.value);  // visit
  inOrder(node.right);
}

Here a node is not printed until its entire left subtree has been:

1   5   3   8

Move the visit line to the bottom, after both recursive calls, and we have post-order:

public static <T> void postOrder(Node<T> node) {
  if (node == null) {
    return;
  }
  postOrder(node.left);
  postOrder(node.right);
  System.out.println(node.value);  // visit
}

Now a node is not printed until both of its subtrees have been:

1   5   8   3

All three are depth-first: each one goes all the way to the bottom of a subtree before it moves on to the next subtree. Merge sort’s recursion goes depth-first in the same way.