Traversals in
Binary Tree
Before reading this, please
check out our video https://www.youtube.com/watch?v=FFOTq1RcrBE to fully
understand what a binary tree actually is.
Now, you must be wondering
that how can we print the data of the tree or how can we actually go to each
node in the tree. So, traversals are the systematic way through which we can
travel to each node in the tree exactly once that too in some systematic
behavior.
The linear order, which traverses
from beginning to end, is not present in the trees.
The different traversals
present for the tree are -
1. Preorder
Traversal
2. Inorder Traversal
3. Postorder
Traversal
4. Level Order
Traversal
Remember that binary tree is
of recursive nature, means that the left and right sub trees of the binary tree
root node are themselves the binary trees and this property helps us achieve
the traversals using the recursion method.
1. Pre order
Traversal-
Steps.
i.
Visit the root
ii.
Traverse the left sub tree in pre order manner
iii.
Traverse the right sub tree in pre order manner
2. In order
traversal
Steps
i.
Traverse the Left sub tree in in order fashion
ii.
Visit the root
iii.
Traverse the right sub tree in in order fashion
3. Post Order
Traversal
Steps
i.
Traverse the left sub tree in post order fashion
ii.
Traverse the right sub tree in post order fashion
iii.
Visit the root
We will discuss the level
order traversal later.
In all the above three
traversals, we can see that the steps involve the traversing the left and right
sub trees in some particular fashion, and here at these steps is when we call
it recursively.
Recursive
implementation of the Traversals –
Structure
of node of a tree
struct node
{
int data;
node *left; //left
child
node *right; //right
child
};
1.
Preorder
void preorder(node *n)
{
if(n==NULL) return ;
// if node is NULL or becomes NULL simply return
//acts as base case
printf("%d\t", n->data); // print the root
preorder(n->left); // recurse over left sub tree
preorder(n->right); //recurse over right sub tree
}
2.
Inorder
void inorder(node * n)
{
if(n==NULL) return ;
inorder(n->left); // recurse over left first
printf("%d\t", n->data); // print node ->data
inorder(n->right); // now recurse over right sub tree
}
3.
Postorder
void postorder(node *n)
{
if(n==NULL) return ;
postorder(n->left);
postorder(n->right);
printf("%d\t", n->data);
}
Time Complexity – O(n) , n =
#nodes in the tree
Space Complexity – O(n) –
considering the stack used in the recursion
Iterative
implementations of the Traversals-
1.
Preorder
void preorderi(node *n)
{
if(n==NULL)
return;
stack<node *>s; // make an explicit stack
s.push(n); //push root node
into it
while(!s.empty()) // while stack has nodes
{
node *temp = s.top(); //print parent/node data
cout<<temp->data;
s.pop();
//push its left and right
children but in opposite order as stack works in LIFO manner
if(temp->right)
s.push(temp->right);
if(temp->left)
s.push(temp->left);
}
}
2.
Inorder
i.
Create an empty stack
ii.
push root node and make it the current node
iii.
keep on pushing node till current does not become
NULL, right now the topmost element in stack is the first node to be printed in
inorder traversal
iv.
now till the stack does not become empty , keep on
popping the top print it and move to the popped node’s right
void inorderi(node *n)
{
if(n==NULL)
return;
stack<node *> s;
int done =0;
while(!done)
{
if(n!=NULL)
{
s.push(n);
n=n->left;
}
else
{
if(!s.empty())
{
n
= s.top();
printf("%d \t",
n->data);
s.pop();
n=n->right;
}
else
{
done =1;
}
}
}
}
3.
Postorder
A little difficult due to
non-tail recursion present in it. We simply generate the reverse Postorder and
store it in the stack and using the LIFO property we print the correct
Postorder traversal.
You may now think that how
to generate the reverse Postorder.
Lets try it out on an
example –
The Postorder traversal is –
4, 5, 2 , 6 , 7 , 3 ,1
The reverse Postorder
Traversal is – 1, 3, 7, 6, 2, 5, 4
We need to get this into the
stack. But Question still remains same … How ??
Let us check Preorder Traversal
– 1, 2, 4, 5, 3, 6, 7
We know that in preorder
first the left subtree is recursed and then right sub tree.
But suppose if we change it
to first recurse over right sub tree and then to over left sub tree
Changed preorder traversal –
1, 3, 7, 6, 2, 5, 4
And now you can easily see
that this changed preorder and reverse post order traversal we want are the
same.
So for iterative Postorder,
we go like preorder with two little changes
i.
Recurse over left first and right later ( remember
context of Stack -LIFO)
ii.
Instead of printing the data, store it in the stack
iii.
At last print the stack
Two stacks will be needed,
one for holding the reverse Postorder and other for iterating over the nodes.
void postorderi(node *n)
{
if(n==NULL)
return;
stack<node *>s1;
stack<node *>s2;
s1.push(n);
while(!s1.empty())
{
node *temp = s1.top();
s1.pop(); //popping form s1
s2.push(temp); //pushing to s2
if(temp->left)
s1.push(temp->left);
//remember LIFO
if(temp->right)
s1.push(temp->right);
}
while(!s2.empty())
{
node *t = s2.top();
printf("%d\t", t->data);
s2.pop();
}
}
These all are the DFS kind
of traversals.
There also exist BFS kind of
traversal known as level order traversal.
We will discuss it soon.
Till time practice these.
For any queries or problems
or future updates, kindly subscribe to our YouTube Channel
Any Queries or
updates or any problem in document or the Videos that you may want to discuss
you can follow our twitter account - https://twitter.com/Logic_Heap
No comments:
Post a Comment