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

}

}