Binary trees in C++ – 6 : preorder traversal – nonrecursive
February 15, 2011 Leave a comment
We now look at another nonrecursive version of the preorder traversal of a binary tree. This time we do not use any additional data structure such as a stack.
Instead we assume that each node has 2 additional fields:
1. a bool flag.
2. a pointer to the parent node. (For the root node, this would be null).
Initially the flags of all nodes are false. We set the flag of a node to be true once we have traversed it.
void preorder ( Node *root)
Node *temp = root;
if (root == (Node*) NULL)
if (temp->flag == false)
//print its data
cout << temp->data <<endl;
temp -> flag = true;
//make temp->left the new temp (if temp->left is not null, and its flag is false)
if (temp->left && !(temp->left->flag))
temp = temp->left;
else if (temp->right && !(temp->right->flag))
//if temp->left is null, then make temp->right the new temp (if temp->right is not //null, and its flag is false).
temp = temp -> right;
else if (temp == root)
//we are done traversing all nodes.
// we are done exploring all nodes in subtree rooted at temp.
// make temp->parent the new temp.
temp = temp -> parent;
As can be seen, not using the stack has resulted in this code taking a seemingly complicated look.