Binary Trees in C++ – 5 : Preorder traversal – nonrecursive

Here we implement a preorder traversal of a binary tree in a non-recursive fashion.

The methodology is as follows: in the recursive version, we are able to accomplish our task very easily because we have an implicit stack data structure with us. So, in order to implement the preorder traversal non-recursively, we shall make explicit use of a stack data structure.

The code is fairly simple to understand.

We assume that we have access to a stack data structure which supports push, pop and is_empty functions.

————

we assume each node of the tree to be of this form:

struct Node

{

int data;

Node *left; //left child pointer

Node *right; //right child pointer

};

void preorder ( Node *root)

{

Stack s;

Node *temp;

s.push (root ) ;

while ( ! s.is_empty() )

// while the stack is not empty

{

temp = s.pop( ); // in the very 1st iteration, root is popped out.

// print the data of temp.

cout << temp->data << endl;

// now push the right child of temp into the stack (if temp does have a right child)

if (temp->right)

s.push (temp->right);

 

// now push the left child of temp into the stack (if left child is not null)

if (temp -> left)

s.push (temp->left)

}

}

—————

At the beginning, the stack only contains the root node. We enter the while loop. In the 1st iteration, the root is popped out, and the data stored in the root is printed. After that, we know that a preorder traversal should print out the nodes in the left subtree of root, followed by the nodes in the root’s right subtree.

Therefore, we push the right child of temp into the stack, followed by the left child of temp.

Now, consider what happens in the next iteration of the while loop. The left child of root which is now the top-most element in the stack is popped out and the data contained in it is printed. This is followed by pushing in its children into the stack. As can be seen, this effectively means that all these nodes now pushed in would be printed before the right child of the root node.

Hence, it can be seen that the preorder traversal property is maintained by the code.

———-

The code runs in O(n) time.

——–

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: