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.

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:

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.

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

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);

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

But above methods are not recursive...

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

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

super coolnice it's easy to understand

Post a Comment