Wednesday, December 22, 2010

Iterative (Non-Recursive) Binary Tree Traversal Algorithms

Tree traversals are very frequent in everyday programming. Recursive implementations are trivial, but they are almost never used in practice. In this post I will implement four most important tree traversals: preorder, inorder, postorder and levelorder. To keep the things simple, I will use binary trees, with a very simple representation:

struct Node
{
    char value;
    Node* left;
    Node* right;
};

Also, I will visit individual nodes with the following following function:

void Visit(Node* node)
{
    cout << node->value;
}

I will use standard C++ and some STL containers. Traversal sequences will be tested on the following simple binary tree.

SimpleTree

As most other recursive algorithms, tree traversals can be easily implemented iteratively by using stack (levelorder is exception, since it is implemented by using the queue). Therefore additional space is used: O(n = number of nodes) in the worst case. Compared to recursion, this is still much better, because we push only necessary data on the stack (recursion additionally puts return address, registers,...). Additionally, stack overflow can't happen because STL containers use heap for storing their elements. Time complexity for all mentioned traversals is O(n).

Preorder Traversal

Expected Output: ABDGLEHICFJKM

Preorder is the simplest iterative tree traversal. We start by pushing the tree root to the stack. Then, until the stack is empty, we repeat the following routine: pop the next node and then push its children to the stack. First right then left, because we want the left sub-tree to be visited first.

void PreorderTraversal(Node* root)
{
    stack<Node*> s;

    if (root != NULL)
    {
        s.push(root);
    }

    while (!s.empty())
    {
        Node* current = s.top();
        s.pop();

        Visit(current);
       
        if (current->right != NULL) s.push(current->right);
        if (current->left != NULL) s.push(current->left);
    }
}

Inorder Traversal

Expected Output: LGDBHEIACJFKM

Inorder traversal is a bit trickier. We want the leftmost node to be visited first. Therefore, root node is pushed to the stack first, followed by its left child, then its leftmost grandchild,... until the leftmost node in the entire tree. Then we pop the nodes one by one. When we pop a node, we know that its left sub-tree has already been visited, so we visit the node itself. Then we push its right node, and similarly to what we have done with the root, we push its left child, then its leftmost grandchild,... until we push its leftmost descendant. Traversal then continues in similar fashion.

void InorderTraversal(Node* root)
{
    stack<Node*> s;

    Node* current = root;

    while (current != NULL)
    {
        s.push(current);
        current = current->left;
    }

    while (!s.empty())
    {
        current = s.top();
        s.pop();

        Visit(current);

        current = current->right;
        while (current != NULL)
        {
            s.push(current);
            current = current->left;
        }
    }
}

Postorder Traversal

Expected Output: LGDHIEBJMKFCA

Postorder is the most difficult tree traversal. It is similar to inorder traversal to some extent, but at the situations when inorder traversal pops and visits the node, postorder leaves the node on the stack and continues visiting its right sub-tree. When it finishes with the right sub-tree it pops the node from the stack and visits it. Obviously, each node is encountered two times, but it is the second time when we actually visit it. Therefore, some mechanism must be used to differentiate between these two situations. Some implementations put an additional flag to Node structure. In our case we don't want to change this structure, so we use an additional stack of bool values. For each element on the node stack, a corresponding value is stored on the bool stack. If this value is true, then we need to pop and visit the node on next encounter.

void PostorderTraversal(Node* root)
{
    stack<Node*> s;
    stack<bool> v;

    Node* current = root;

    while (current != NULL)
    {
        s.push(current);
        v.push(false);
        current = current->left;
    }

    while (!s.empty())
    {
        current = s.top();
       
        bool alreadyEncountered = v.top();
        if (alreadyEncountered)
        {
            Visit(current);
            s.pop();
            v.pop();
        }
        else
        {
            v.pop();
            v.push(true);

            current = current->right;
            while (current != NULL)
            {
                s.push(current);
                v.push(false);
                current = current->left;
            }
        }
    }
}

Levelorder Traversal

Expected Output: ABCDEFGHIJKLM

Levelorder traversal implementation is very similar to the preorder implementation, with the most significant difference that now the queue is used instead of stack.

void LevelorderTraversal(Node* root)
{
    queue<Node*> q;

    if (root != NULL)
    {
        q.push(root);
    }

    while (!q.empty())
    {
        Node* current = q.front();
        q.pop();

        Visit(current);

        if (current->left != NULL) q.push(current->left);
        if (current->right != NULL) q.push(current->right);
    }
}

8 comments:

Anonymous said...

Your algorithms work fine, however you're missing the point of wanting to do an iterative binary tree traversal. Which is saving memory. Using recursion you build up stack frames each time you call yourself and that can get expensive. On the other hand the code is extremely simple. What you are doing is essentially emulating the stack frames with the stacks you are using and not really saving any memory and yet still losing the elegant algorithm you get with recursion.

Uros Vidojevic said...

Hi, thanks for the comment!

I agree with your observations that my code still uses additional memory (like recursion) and is more complex (than recursion).

However, I still wanted to demonstrate these algorithms becase they have a couple of important advantages over recursion:
1.) These algorithms use less space than recursion. They use stack to store Node pointers only. Recursion uses stack to store additional things, such as return address, registers,...
2.) With recursion you can easily get stack overflow when all stack frames add up to more than let's say 1MB (on Windows). On the other hand, everything I add to my stack is stored on the heap. (I know that the stack variable is stored on the program stack, but still everything you add to it is stored on the heap). Therefore, with these algorithms, it takes much longer to run out of memory. They would run out of memory only when the process runs out of virtual address space.
3.) As far as I know, there is no way to traverse a tree in O(1) memory if tree nodes contain just child pointers. We would have to add a parent pointer to achieve that. But even then we are using additional O(n) space (parent pointers) :-) .

Thanks,
Uros

Anonymous said...

is is excellent work. It was fun to read. The post-order must process a every node twice before visiting it. If a tree has all left nodes, then they will need to be processed before getting visited.
you can optimize it as follow: v.push(current->right == null); instead of v.push(false);

Anonymous said...

Have a look at Sedgewicks critic of recursive methods, complexity is exp(n). Why would you ever want to use recursion unless answering an interview question. Note, not all tree recursives algorthims can be emulated via using tail recursion.

Anonymous said...

@Anonymous

But above methods are not recursive...

Furthermore how can you claim that recursive methods in general have exp(n) time complexity?

Anonymous said...

This is absolutely the best iterative binary tree traversal tutorial on the net. Code samples are excellent too. Thanks a million!

Anonymous said...

super cool

Anonymous said...

nice it's easy to understand