Home » Data Structure & Algorithms » PreOrder Traversal of Binary Tree

PreOrder Traversal of Binary Tree

Question :
WAP to Print PreOrder Traversal of tree in O(n) time complexity.

Example Binary Tree :

 

 

Solution :
The problem is solved in both recursive and iterative way.
PreOrder traversal of tree means to traverse the tree in left->root->right manner.

Recursive Algorithm :
Here we are traversing the left sub tree then root and then right sub tree.We are existing on null value of node .

Iterative Algorithm :
Since we need to print node 8 first.We are traversing form root till to the left most element of tree.We are inserting each element in a stack while traversing.After that we are checking if stack is empty or not.If it is not
empty we are printing the top element of the stack and poping the top element and making current element as right element of current element.

Let’s do a dry run.
Node 1 has left ? Yes then put Node 1 in stack and go to left of Node 1 i.e. Node 2.
Node 2 has left ? Yes then put Node 2 in stack and go to left of Node 2 i.e Node 4.
Node 4 has left ? Yes then put Node 1 in stack and go to left of Node 4 i.e Node 8.
Node 8 has left ? No then check if stack is empty.It is not empty.
Retrieve the top element of stack i.e Node 8.Print it.Pop it out.Enter its right node.But Node 8
has no right child.We print the top element of stack again as it is not empty.
Node 4 is printed.Node 4 has right child i.e Node 9.Node 9 is inserted into stack and it is printed.
This way gradually we reach the root i.e Node 1.
Node 1 has right child Node 3 and Node 3 has left child Node 6.
So from Node 8 to root 1 how the above algorithm works,similar form Node 6 same algorithm will work.

 


Leave a comment

Your email address will not be published. Required fields are marked *

two + seventeen =