Traversing Binary Trees

To traverse a tree means to visit all the nodes in the tree and perform an operation at each node.

For a binary tree, there can only be at most two children for each node, so a common Java class to represent a node can be as follows:

class Node {
    int data;
    Node left;
    Node right;
}

An efficient way to traverse a tree is to use recursion. For a binary tree, the recursive traversal method can be represented as follows:

traversal_method(node) {
    if node is null 
        return

    traversal_method(left child node) 
    do_something(node)
    traversal_method(right child node)
}

The first recursive call traversal_method(left child node) traverses the left child node and its children.

The second recursive call traversal_method(right child node) traverses the right child node and its children.

The placement of the do_something(node) line determines the type of traversal, and there are three types of tree traversal: in-order, pre-order, and post-order.

A useful way remember the tranversal types is to think where the do_something(node) line is placed relative to the two recursive calls.

• In-order: do_something(node) is placed in-between the two recursive calls.
• Pre-order: do_something(node) is placed before the two recursive calls.
• Post-order: do_something(node) is placed after the two recursive calls.

In-Order Traversal #

For in-order traversal, the left child node is visited first, then the current node, and then the right child node.

The in-order traversal of a tree can be represented as follows:

inOrderTraversal(node) {
    if (node == null) {
        return;
    }
    inOrderTraversal(node.left);
    System.out.println(node.data);
    inOrderTraversal(node.right);
}

The diagram below shows the nodes of a tree being visited in the order of an in-order traversal. The println statment will be called at node in the numerical order shown.

Pre-Order Traversal #

For pre-order traversal, the current node is visited first, then the left child node, and then the right child node.

The pre-order traversal of a tree can be represented as follows:

preOrderTraversal(node) {
    if (node == null) {
        return;
    }
    System.out.println(node.data);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
}

The diagram below shows the nodes of a tree being visited in the order of a pre-order traversal. The println statment will be called at node in the numerical order shown.

Post-Order Traversal #

For post-order traversal, the left child node is visited first, then the right child node, and then the current node.

The post-order traversal of a tree can be represented as follows:

postOrderTraversal(node) {
    if (node == null) {
        return;
    }
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    System.out.println(node.data);
}

The diagram below shows the nodes of a tree being visited in the order of a post-order traversal. The println statment will be called at node in the numerical order shown.