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)

return;

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.

break;

else

// 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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: