Binary trees in C++ – 6 : preorder traversal – nonrecursive

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.


struct Node


int data;

Node *left;

Node *right;

Node *parent;

bool flag;


void preorder ( Node *root)


Node *temp = root;

if (root == (Node*) NULL)


while (true)


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.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: