12.1-3
Give a nonrecursive algorithm that performs an inorder tree walk. (
Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)
Following code snippet is implementing the inorder traversal in recursive manner:
void inorder_tree_walk(struct node *t)
{
if (t != NULL) {
inorder_tree_walk(t->left);
process(t);
inorder_tree_walk(t->right);
}
}
There are two recursive calls to
inorder_tree_walk() and both can be eliminated. First, we can remove the second one at line 6 by using tail call elimination technique as following:
void inorder_tree_walk(struct node *t)
{
start: if (t == NULL) goto end;
inorder_tree_walk(t->left);
process(t);
t = t->right; goto start;
end:
}
The first call also can be removed by introducing a stack for storing the current context.
void inorder_tree_walk(struct node *t)
{
stack<struct node *> s;
start: if (t == NULL) goto pop;
s.push(t); t = t.left; goto start;
pop: if (s.empty()) goto end;
t = s.pop();
process(t);
t = t->right; goto start;
end:
}
Now that the recursive calls are removed, code can be further simplified by removing dirty
goto statements. The code between the first
if statement and the first
goto start is nothing more than a while loop. The label
end can also be removed.
void inorder_tree_walk(struct node *t)
{
stack<struct node *> s;
start: while (t != NULL) {
s.push(t);
t = t.left;
}
if (!s.empty()) {
t = s.pop();
process(t);
t = t->right;
goto start;
}
}
Looking at the overall flow of the program, the remaining
goto statement can be converted into an outer
while loop. Therefore, we finally get the following code:
void inorder_tree_walk(struct node *t)
{
stack<struct node *> s;
while (1) {
while (t != NULL) {
s.push(t);
t = t.left;
}
if (s.empty()) break;
t = s.pop();
process(t);
t = t->right;
}
}
As mentioned in the problem statement, there exists another solution without using either stack or recursion. It is called as Morris inorder traversal, which uses the threaded binary tree.
void morris_inorder_walk_tree(struct node *t)
{
while (t != NULL) {
if (t->left == NULL) {
/* no more left child, process it and go right */
process(t);
t = t->right;
} else {
/*
* before going to the left, make the right-most node
* of left child point to the current. Not only that,
* we should check if we already visited the left to
* prevent getting stuck in an infinite loop.
*/
struct node *p = t->left;
while (p->right != NULL && p->right != t)
p = p->right;
if (p->right == NULL) {
p->right = t;
t = t->left;
} else {
/* restore the pointer back */
p->right = NULL;
process(t);
t = t->right;
}
}
}
}
