Tuesday, November 15, 2011

Iterative traversal of a binary search tree

A binary tree is a simple yet beautiful structure.
One of its most compelling features is sorting, which directly relies on the binary search tree property.
Here is an example of printing a sorted tree:
void printBinaryTreeInOrder (Node cursor)
{
    printBinaryTreeInOrder (cursor.leftChild);
    print (cursor.value + ", ");
    printBinaryTreeInOrder (cursor.rightChild);
}
Nice and easy.
However, it is a bit harder to use an iterative approach to the same problem.
The solution is essentially keeping track of your own call stack while the method executes.
A few words aside.
In a classical von Neumann machine, data and program instructions can be stored in same memory.
A working recursive function allocates stack memory (which is most likely in RAM) every time a new call is made.
For an iterative solution, we will also keep track of the visited nodes in a stack.
So to really understand how the code below works, write out a simple tree on a piece of paper and trace the order in which each node is visited by the recursive function.
Here is the little piece of iterative magic:
void printBinaryTreeInOrder
{
    Node cursor = root;
    Stack  iteratorStack = new Stack  ();
    while (iteratorStack.notEmpty() || cursor)
    {
        if (cursor)
        {
            iteratorStack.push(cursor);
            cursor = cursor.leftChild;
        }
        else
        {
            cursor = iteratorStack.pop();
            print(cursor.key);
            cursor = cursor.rightChild;
        }
    }
}
In essence, we walk the tree from the root.
First, we go all the way to the left-est node, pushing all the nodes we passed on the way there onto the stack.
The node at the far left is the smallest, that's the one we want to print first.
When we call for the left child again, we get null in return.
We go on to the else clause, grabbing the last valid node from the stack and printing it.
Afterwards, we shift to the right node of the cursor and happily chug along.

No comments:

Post a Comment