Binary Tree Traversal

Standard

I thought long before of writing this post after discussing the binary tree generation in reverse lexicographic order but unfortunately it got delayed. So lets not make any more delay in discussing binary tree traversal.

Following are the general way of traversing binary tree, which you can find in any data structure book:-

1) Preorder :-

sample recursive code:

preorder(node)
{
           if(node!=null)
           {
                visit(node);
                preorder(left(node));
                preorder(right(node));
           }
}

Non-recursive traversal:-

preorder(root)
{
            p=root;
            stack S;
            while(p is not null or S is not empty) 
            {
              if(p is not null)
              {
                    visit(p);
                    push(p,S);
                    if(left(p) is not null)
                            p=left(p);
                   else
                            p=right(p);
             }
             else
             {
                      do
                     {
                           q=S.pop();
                           if( S is not empty)
                                rtptr=right(item(S));
                           else
                                 rtptr=null
                     }while(S is not empty and q is rtptr);
                     p=rtptr;
           }

}

2) Inorder :-

inorder(node)
{
         if(node!=null)
         {
             inorder(left(node));
              visit(node);
             inorder(right(node));
        }
}

3) Postorder :-

postorder(node)
{
       if(node!=null)
       {
             postorder(left(node))
             postorder(right(node));
             visit(node);
        }
}

4) Level-wise binary tree traversal.

We can have some more traversal based on the way we traverse left and right child. But here all the traversal require some extra data structure like stack. Hence we will discuss some more tree traversal which are space effective.

Link Inversion Traversal

This is very space effective and beautiful algorithm. In which we assign 1 bit extra information which store  0 or 1.  Initially, all the node have 0. As we descend to the right, we tag that node as 1 and make the right pointer of the node point to parent, whose right subtree is to be traversed. And as we descend to the left, we tag that node as 0 and make the left pointer point to parent, whose left subtree is to be traversed. Once we finish the traversing the subtree, can look at the tag of the node and decide whether it was the left or right subtree of the parent whose traversal has just been finished, this way we traverse back up to root. While traversing, we should restore the tag and its pointers also.

This tree traversal does not require any additional data structure and it just need n extra bit to tag each node. Lets improve this also.

Robson Traversal

This is even more space effective than the “Link Inversion Traversal”, since it does not require even  n bits extra information. It uses the leave node to store the information, basically it connects all the leave node and use them as stack and hence we need an extra pointer to point to start or end of this stack and we call that pointer as stack and one more extra pointer we will call that top,which will point to the last (recent) traversed node whose right tree we are traversing and which have non null left subtree and stack pointer’s right will point to the next most recent and its left pointer will point to the next leave node who will store the similar information.

Here is the algorithm:-

Hello world!

Standard

Hi Guys,

I am Aakash, currently a graduate student at Temple University, Philadelphia before joining Temple I worked as Senior Quality Eng. in Yahoo! R&D for 3 and half years. I am also an alumni of Vellore Institute of Technology, Vellore, India.
I believe in working hard and doing something new in my style. I am fond of computers and love solving problems, optimizing it and my area of interests are: Programming Technique. Algos, Operating System and Distributed Systems.
As far as my hobbies and interests are concerned I like coding, reading books, listening songs and watching Cricket and Football.

I will welcome readers to be my friend at FB (https://www.facebook.com/profile.php?id=750863707) and will appreciate their comments.

Thanks for ur precious time!