Traversal

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.

Three common orders in BST traversal:

1. Pre-order
2. In-order
3. Post-order

Pre-order Traversal

Visit (Node current){
    if (current == null)
        return;
    Process(current.Value);
    Visit(current.Left);
    Visit(current.Right);
}

// result: 4 2 1 3 6 5 7

In-order Traversal

Visit (Node current){
    if (current == null)
        return;
    Visit(current.Left);
    Process(current.Value);
    Visit(current.Right);
}

// result: 1 2 3 4 5 6 7

Post-order Traversal

Visit (Node current){
    if (current == null)
        return;
    Visit(current.Left);
    Visit(current.Right);
    Process(current.Value);
}

// result: 1 3 2 5 7 6 4