Iterative traversals for Binary Trees

Knowledge of tree traversals is very important in order to completely understand Binary Trees. Though the recursive implementation of tree traversals, can be coded very neatly but
recursion is generally not preferred. Excessive recursive function calls may
cause memory to run out of stack space.Since the depth of a balanced binary search tree is about lg(n), we need not
worry about running out of stack space, even if there are a million elements
in the tree. But alas perfectly balanced trees, come at their own cost. Rather
efficient height balanced trees is still an active area of interest. So it is
quite possible in practical scenarios that the tree may not be balanced. If
that is the scenario then we are asking for trouble using recursion, because
in the worst case the height of the tree may go up to n and in this case, the
stack space will eventually run out and the program will crash.Iterative tree traversals can be coded easily, using a _ visited _ flag. This
has been sufficiently explained atthis wiki page. But this
requires us to change the structure of the tree, and we would not want that.
Here we will attempt to develop iterative traversals, without modifying the
structure.Understanding the below given iterative traversals can be a little tricky so
the best way to understand them is to work them out on a piece of paper. Use
this sample binary tree and follow the steps of the below given codes.In Order Traversal:The in order traversal requires that we print the leftmost node first and the
right most node at the end. So basically for each node we need to go as far as
down and left as possible and then we need to come back and go right. Steps of
algorithm are:> 1. Start with the node equals root> 2. Store the node in the stack and visit it’s left child.> 3. Repeat step 2 while node is not NULL, if it’s NULL then pop it’s parent
(i.e. the last node in stack) and print it.> 4. Now move to node’s right child and repeat step 1> 5. Repeat whole procedure while node is not NULL and stack is not emptyInorder(Tree *p)
{
stack < Tree* > S;
do
{
while (p!=NULL)
{
// store a node in the stack and visit it’s left child
S.push(p);
p=p->left;
}

// If there are nodes in the stack to which we can move up
// then pop it
if (!S.empty())
{
p=S.top();
S.pop();

// print the nodes value
cout << p->ele << “-“;

// vistit the right child now
p=p->right;
}

// while the stack is not empty or there is a valid node
}while(!S.empty()||p!=NULL);
}Food for Thought:The above given iterative solution makes use of explicit
stack. We have only managed to eliminate the recursion, but not the extra
space requirement. Can there be another way in which we can give an in-order
traversal without using a stack?Yes! you can do that and there are two methods. But both of them require to
change the tree structure as we generally us it.> * One is pretty intuitive, and that is to have a parent pointer, in
addition to the child pointer. This eliminates the need for extra space,
because the whole purpose of using a stack was to save the parent nodes.> * The second is not so intuitive, but a very popular data structure and
that isThreaded Binary Tree. This along with
the normal structure, also stores a pointer to the next in-order successor of
a node. In case there is a right child then the in-order successor is the
child otherwise it is one of the successors.Pre Order Traversal:Pre order is very similar to in order traversal. The way of accessing all the
nodes remains the same except the position where we print the node. Now the
node is printed/visited before visiting the children of the nodes. Steps are
very similar to in-order> 1. Start with node equal to root node> 2. Store the node in the stack, print it and visit it’s left child.> 3. Repeat step 2 while node is not NULL, if it’s NULL then pop it’s parent
(i.e. the last node in stack).> 4. Now move to node’s right child and repeat step 2> 5. Repeat whole procedure while node is not NULL and stack is not emptyPreorder(Tree *p)
{
stack < Tree* > S;
do
{
while (p!=NULL)
{
// storea node in stack and print it’s value
S.push(p);
cout << p->ele << “-“;
// visit the left child
p = p->left;
}

// visit the right child
if (!S.empty())
{
p=S.top();
S.pop();
p = p->right;
}

} while(!S.empty()||p!=NULL);
}Post Order Traversal:Post order traversal is the trickiest one, out of all the three traversals. However post order traversal is important to understand because of the following 2 use cases> * Tree deletion: In order to free up allocated memory of all nodes in a
tree, the nodes must be deleted in the order where the current node is deleted
when both of its left and right sub-trees are deleted. This can be done using
post-order traversal only.> * It is also used in evaluatingPost-fix or Reverse Polish Notation.The problem with post-order traversal is that in the previous two cases when a
node was popped of from the stack, then it was finally removed and was not
accessed again. However in case of post-order the node needs to be accessed
from the stack twice, and is deleted only in the second access.First time we find a node, we push it on to the stack, the second time we
examine it from the stack to go to it’s right child and then finally after
visiting both the right sub-tree and the left-subtree we remove the node from
the stack. So a node stays in the stack as long as it’s sub-trees have not
been visited.> Since, a node has to be visited(printed in the trivial case) only after it’s
left and right child have been visited, we print a node’s value after we have
visited the left child followed by the right child. The property that is
exploited in this implementation is that the the parent node will always be
visited just after visiting it’s right child.After visiting the left child, when we come to the parent node in the stack if
the right child is NULL, then we can straight away print the node, but if it’s
not NULL then we have to check whether the previous node which was printed is
it’s right child. If it’s the right child then we can visit the current node,
otherwise the right child has not been visited and we must proceed with the
right child.Hence in this traversal, we have to use a previous pointer, only then will we
able to correctly traverse the node. Otherwise we do not know when the right
child has been visited or not.> 1. Start with the root node.> 2. Store the node in the stack, and visit it’s left child.> 3. Repeat step 1 while node is not NULL, if it’s NULL:> * Pick the top most node from the stack.> * If it’s right child is NULL, then print the node and set prev pointer
to this node> * If it’s not NULL, check whether the right child is equal to prev
pointer, if it is then print the node, else repeat step 1 with the right child> * In this step, if you print the node then current is made equal to NULL
and this sub-loop is repeated untill stack is not empty and current is NULL> 4. Since the root node remains in the stack till the end, the terminating
condition is untill stack is emptyPostorder(Tree *p)
{
stack < Tree* > S;
Tree *prev = NULL;
do
{
while (p!=NULL)
{
S.push(p);
p = p->left;
}
while(p == NULL && !S.empty())
{
p = S.top();
if(p->right == NULL || p->right == prev)
{
cout << p->ele << “-“;
S.pop();
prev = p;
p = NULL;
}
else
p = p->right;
}
}while(!S.empty());
}

News Reporter

Leave a Reply

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