As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive method for traversal, it need to be an iterative process; meaning, all of steps for the traversal of a node need to be under a loop so that the similar can be applied to all the nodes in the tree.
Algorithm: Non-recursive preorder binary tree traversal
Stack S
push root onto S
repeat until S is empty
{
v = pop S
if v is not NULL
visit v
push v's right child onto S
push v's left child onto S
}
Program 5 illustrates the program segment for the implementation of non- recursive preorder traversal.
/* preorder traversal of a binary tree, implemented via a stack */
void preorder(binary_tree_type *tree)
{
stack_type *stack;
stack = create_stack();
push(tree, stack); /* push the first element of the tree onto the stack */
while (!empty(stack))
{
tree = pop(stack);
visit(tree);
push(tree->right, stack); /* push right child onto the stack */
push(tree->left, stack); /* push left child onto the stack */
}
}