Depth-First Traversals

A binary tree is built from Node objects. Each node holds a value and references to its left and right subtrees. A null reference is the empty tree:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;
}

To visit a node means to print its value.

Solution

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

Solution

Only the position of the print line changes. For pre-order, move it above the two recursive calls. For post-order, move it below both recursive calls.

Here is a binary tree:

              ╭───╮
              │ 4 │
              ╰─┬─╯
       ┌────────┴───────┐
     ╭─┴─╮            ╭─┴─╮
     │ 7 │            │ 1 │
     ╰─┬─╯            ╰─┬─╯
  ┌────┴────┐           └─────┐
╭─┴─╮     ╭─┴─╮             ╭─┴─╮
│ 3 │     │ 9 │             │ 6 │
╰───╯     ╰─┬─╯             ╰─┬─╯
        ┌───┘            ┌────┴────┐
      ╭─┴─╮            ╭─┴─╮     ╭─┴─╮
      │ 2 │            │ 8 │     │ 5 │
      ╰───╯            ╰───╯     ╰───╯

Node 9 has only a left child, and node 1 has only a right child.

Solution

pre-order:    4   7   3   9   2   1   6   8   5
in-order:     3   7   2   9   4   1   8   6   5
post-order:   3   2   9   7   8   5   6   1   4