How to traverse binary trees iteratively?
As we are dealing with the data structures, eventually we will need to traverse them to apply our algorithms. While the breadth first search algorithms require the FIFO (First In First Out) data structure, the depth first search algorithms require the function recursion to apply traversal.
You’ll find the details of the iterative tree traversal methods in this article. Don’t worry, I am not going to copy and paste generic code segments into the article to do so, rather I will share some hints for them to explain intuitively.
The recursion either can be applied via function calls or LIFO (Last In First Out) (aka stack) data structures, and the implementation of the recursion might be tricky based on the complexity of the code we would like to convert into the iterative one. Let’s go into the sample codes for more details.
The code segment on the left depicts pre-order, in-order, and post-order traversal techniques on a binary tree as the function recursions. This is a regular standard recursion method, and by changing the position of visiting the node, (as in lines 11, 20, 29), you can easily change the type of the traversal. Intuitive, easy to remember (or reconstruct from existing knowledge). Now, let’s go ahead and try to implement them iteratively.
struct tree_node {
tree_node() : left(NULL), right(NULL) {}
tree_node(int x) : val(x), left(NULL), right(NULL) {}
int val;
struct tree_node *left, *right;
};
void preorder(tree_node *root)
{
if (root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(tree_node *root)
{
if (root == NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(tree_node *root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
We can see the iterative traversal methods on the left. Our first example is the pre-order traversal. The code layout is similar to the recursive approach as in the previous example except for the line 10 and 11. Due to the nature of the iteration with a stack, we need to push the right pointer first to process the left sub-tree first. Remember the stack is a LIFO (Last In First Out) type data structure.
Next example is the in-order traversal. Although it has a few lines of the code, this one is a little bit confusing. The main idea of this approach is to lean left until the edge of the tree, visit the node, jump right sub-tree, then continue until the point there is nothing left in the stack to process.
Our last two examples show how to conduct post-order traversals using one and two stack(s).
In one stack method, we need to keep two variables to hold the last visited node (lastNodeVisited) along with the node (peekNode) we want to visit. As you can image this is very confusing, and even you memorize each line of the algorithm, it is hard to justify.
As to two stacks method, we first conduct inverse pre-order traversal to glean all the nodes into the Result stack, then we reclaim these nodes from it so they get printed in a correct order. This is relatively a simple solution, but it has one important drawback. In this method we need to wait for all the nodes to be populated into the temporary memory (Result stack) so it is impossible to visit the node for each step. If you need to use a callback function to achieve specific task for every traverse step, this method is useless.
We need a solution not only elegant but also adhere the sequence of the traversal so we can process the node during the visit.
void preorder_iterative(tree_node *root)
{
if (root == NULL) return;
stack<tree_node *> S;
S.push(root);
while (S.size()) {
tree_node* curr = S.top(); S.pop();
cout << curr->val << " ";
if (curr->right) S.push(curr->right);
if (curr->left) S.push(curr->left);
}
}
void inorder_iterative(tree_node *root)
{
stack<tree_node *> S;
while (S.size() || root) {
if (root) {
S.push(root);
root = root->left;
} else {
root = S.top(); S.pop();
cout << root->val << " ";
root = root->right;
}
}
}
void postorder_iterative_one_stack(tree_node *root)
{
stack<tree_node *> S;
tree_node *lastNodeVisited = NULL;
while (S.size() || root) {
if (root) {
S.push(root);
root = root->left;
} else {
tree_node *peekNode = S.top();
// if right child exists and traversing node
// from left child, then move right
if (peekNode->right && lastNodeVisited != peekNode->right) {
root = peekNode->right;
} else {
cout << peekNode->val << " ";
lastNodeVisited = S.top(); S.pop();
}
}
}
}
void postorder_iterative_two_stack(tree_node *root)
{
if (root == NULL) return;
stack<tree_node *> R; // Result
stack<tree_node *> S;
S.push(root);
while (S.size()) {
tree_node* curr = S.top(); S.pop();
R.push(curr);
if (curr->left) S.push(curr->left);
if (curr->right) S.push(curr->right);
}
while (R.size()) {
tree_node *node = R.top(); R.pop();
cout << node->val << " ";
}
}In order to implement the recursion iteratively, we need to track the state of the nodes while we are pushing them into the stack. Keep in mind during a regular recursion, we keep the execution state in the function call stack implicitly. Therefore we need to create a context structure to emulate the call stack. Rest of the operation is to write the code regarding the necessary transformation for the specific traversal type. You can see the associated stack states for both initialization and execution on the right table. As it can be seen on the actual implementation on the code segments below, a simple state machine has been implemented to create the necessary transformation to achieve desired traversal type.
void preorder_iterative_context_based(tree_node* root)
{
if (root == NULL) return;
enum STATUS { PROCESS = 0, DONE };
stack<pair<tree_node *, STATUS>> S;
S.push({root, PROCESS});
/*
1: Neccessary transform for preorder traversal
initial stack state stack state during traversal
| | | |
| | | |
| | | root, DONE |<top
| |--->| root->left, PROCESS |
top>| root, PROCESS | | root->right, PROCESS |
|-------------------| |--------------------------|
*/
while (!S.empty()) {
auto ctx = S.top(); S.pop();
switch (ctx.second) {
case (DONE) : {
cout << ctx.first->val << " ";
} break;
case (PROCESS) : {
if (ctx.first->right) S.push({ctx.first->right, PROCESS});
if (ctx.first->left) S.push({ctx.first->left, PROCESS});
if (ctx.first) S.push({ctx.first, DONE});
} break;
default : ;
}
} // end-while
}
void inorder_iterative_context_based(tree_node* root)
{
if (root == NULL) return;
enum STATUS { PROCESS = 0, DONE };
stack<pair<tree_node *, STATUS>> S;
S.push({root, PROCESS});
/*
2: Neccessary transform for inorder traversal
initial stack state stack state during traversal
| | | |
| | | |
| | | root->left, PROCESS |<top
| |--->| root, DONE |
top>| root, PROCESS | | root->right, PROCESS |
|-------------------| |--------------------------|
*/
while (!S.empty()) {
auto ctx = S.top(); S.pop();
switch (ctx.second) {
case (DONE) : {
cout << ctx.first->val << " ";
} break;
case (PROCESS) : {
if (ctx.first->right) S.push({ctx.first->right, PROCESS});
S.push({ctx.first, DONE});
if (ctx.first->left) S.push({ctx.first->left, PROCESS});
} break;
default : ;
}
} // end-while
}
void postorder_iterative_context_based(tree_node* root)
{
if (root == NULL) return;
enum STATUS { PROCESS = 0, DONE };
stack<pair<tree_node *, STATUS>> S;
S.push({root, PROCESS});
/*
3: Neccessary transform for postorder traversal
initial stack state stack state during traversal
| | | |
| | | |
| | | root->left, PROCESS |<top
| |--->| root->right, PROCESS |
top>| root, PROCESS | | root, DONE |
|-------------------| |--------------------------|
*/
while (!S.empty()) {
auto ctx = S.top();
switch (ctx.second) {
case (DONE) : {
cout << ctx.first->val << " ";
S.pop();
} break;
case (PROCESS) : {
S.top().second = DONE;
if (ctx.first->right) S.push({ctx.first->right, PROCESS});
if (ctx.first->left) S.push({ctx.first->left, PROCESS});
} break;
default : ;
}
} // end-while
}
I tried to explain the iterative recursion approach by emulating the call stack as lucid as possible so hopefully this helps not only to grasp the nature of the recursion but also to implement it into the resource limited embedded controllers. When you deal with a microcontroller which has very limited stack size, implementing the recursive algorithms would be challenging, even sometimes impossible. I hope this article would be helpful to grasp the recursion effectively.
As being said: In order to understand the recursion, first you need to understand the recursion!
Reference(s) :
https://en.wikipedia.org/wiki/Tree_traversal