Binary tree

In computer science, a binary tree is a type of tree data structure where each item within the tree has at most two children.

Traversals

Traversals of an example tree:

Pre-order (red): F, B, A, D, C, E, G, I, H

In-order (yellow): A, B, C, D, E, F, G, H, I

Post-order (green): A, C, E, D, B, H, I, G, F

Pre-order

The current item is visited, then the left branch is visited, and then the right branch is visited.

void preOrder(Item item) {
    if (item == null) return;
    visit(item);
    preOrder(item.left);
    preOrder(item.right);
}

In-order

The left branch is visited, then the current item is visited, and then the right branch is visited.

void inOrder(Item item) {
    if (item == null) return;
    inOrder(item.left);
    visit(item);
    inOrder(item.right);
}

Post-order

The left branch is visited, the right branch is visited, and then the current item is visited.

void postOrder(Item item) {
    if (item == null) return;
    postOrder(item.left);
    postOrder(item.right);
    visit(item);
}