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:-


If the node's left subtree is being traversed, then
        its left pointer is pointing to its predecessor, and its right pointer is undisturbed.

If the node's right subtree is being traversed, then
        if the node has a null left subtree, then
                its right pointer is pointing to its predecessor
        else
                its left pointer is pointing to its predecessor, and its right pointer is pointing   to the root of the node's left subtree.


Here is the java implementation of above discussed tree traversal:-

package edu.temple.pt.assignment;
/**
 * 
 * @author aakash
 *
 * @param  <  T  &rt;   
 */
public class Node <  T  &rt;    {

	/*
	 * taking one extra tag data for link inversion traversal, not needed in any other traversal.
	 */
	private int tag=0;
	public int getTag() {
		return tag;
	}
	public void setTag(int tag) {
		this.tag = tag;
	}


	private T data;
	private Node <  T  &rt;    lt=null;
	private Node <  T  &rt;    rt=null;
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node <  T  &rt;    getLt() {
		return lt;
	}
	public void setLt(Node <  T  &rt;    lt) {
		this.lt = lt;
	}
	public Node <  T  &rt;    getRt() {
		return rt;
	}
	public void setRt(Node <  T  &rt;    rt) {
		this.rt = rt;
	}
	
	public Node(T data) {
		this.data=data;
		this.tag=0;
		// TODO Auto-generated constructor stub
	}
	/**
	 * @param data
	 * @param lt
	 * @param rt
	 */
	public Node(T data, Node <  T  &rt;    lt, Node <  T  &rt;    rt) {
		super();
		this.data = data;
		this.lt = lt;
		this.rt = rt;
		this.tag=0;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((data == null) ? 0 : data.hashCode());
		result = prime * result + ((lt == null) ? 0 : lt.hashCode());
		result = prime * result + ((rt == null) ? 0 : rt.hashCode());
		return result;
	}
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node <  T  &rt;    other = (Node <  T  &rt;   ) obj;
		if (data == null) {
			if (other.data != null)
				return false;
		} else if (!data.equals(other.data))
			return false;
		if (lt == null) {
			if (other.lt != null)
				return false;
		} else if (!lt.equals(other.lt))
			return false;
		if (rt == null) {
			if (other.rt != null)
				return false;
		} else if (!rt.equals(other.rt))
			return false;
		return true;
	}
	@Override
	public String toString()
	{
		StringBuilder sbr=new StringBuilder();
		sbr.append("[");
		sbr.append("{data:").append(data.toString());
//		sbr.append(" tag:").append(tag);
		sbr.append("}");
		if(lt!=null)
			sbr.append(",{left:").append(lt.getData()).append("}");
		else
			sbr.append(",{left:").append(lt).append("}");
		if(rt!=null)
			sbr.append(",{right:").append(rt.getData()).append("}");
		else
			sbr.append(",{right:").append(rt).append("}");
		/*
		if(lt!=null)
			sbr.append(",{left:").append(lt.toString()).append("}");
		else
			sbr.append(",{left:").append(lt).append("}");
		if(rt!=null)
			sbr.append(",{right:").append(rt.toString()).append("}");
		else
			sbr.append(",{right:").append(rt).append("}");
		*/
		sbr.append("]");
		return sbr.toString();
	}

	
	public static void main(String args[])
	{
		System.out.println(new Node <  Integer  &rt;   (new Integer(10)).toString());
	}	
}

package edu.temple.pt.assignment;


import java.util.Stack;
/**
 * 
 * @author aakash
 *
 * @param  <  T  &rt;   
 */
public abstract class BinaryTree <  T  &rt;    {

	protected Node <  T  &rt;    root=null;
	public Node <  T  &rt;    getRoot() {
		return root;
	}

	public void setRoot(Node <  T  &rt;    root) {
		this.root = root;
	}

	protected abstract Node <  T  &rt;    createTree();
	
	public void postOrderTraversal()
	{
		
	}
	public void inOrderTraversal()
	{
		
	}
	public void preOrderTraversal()
	{
		System.out.println("\n=============================");
		System.out.println("Preorder traversal::");
		System.out.println("===============================");
		Node <  T  &rt;    p=root;
		Stack <  Node <  T  &rt;     &rt;    stack=new Stack <  Node <  T  &rt;     &rt;   ();
		while(p!=null||!stack.isEmpty())
		{
			Node <  T  &rt;    rtptr=null;
			if(p!=null)
			{
				visit(p);
				stack.push(p);
				if(p.getLt()!=null)
					p=p.getLt();
				else
					p=p.getRt();
			}
			else
			{
				Node <  T  &rt;   q=null;
				do
				{
					q=stack.pop();				
					if(!stack.isEmpty())
						rtptr=stack.peek().getRt();
					else
						rtptr=null;
				}
				while(!stack.isEmpty()&&q==rtptr);
				p=rtptr;
			}
		}
	}
	public void visit(Node <  T  &rt;    data)
	{
		System.out.println(data.toString());
	}
	
	public void visit(Node <  T  &rt;    data,Node <  T  &rt;    stack,Node <  T  &rt;    top)
	{
		System.out.println("node visiting currently::"+data.toString());
		if(stack!=null)
		{
			Node <  T  &rt;    p=stack;
			System.out.println("Stack::");
			while(p!=null)
			{
				System.out.print("\tdata:"+p.getData());
				if(p.getLt()!=null)
					System.out.print("\t left:"+p.getLt().getData());
				else
					System.out.print("\t left:"+p.getLt());
				if(p.getRt()!=null)
					System.out.println("\t right:"+p.getRt().getData());
				else
					System.out.println("\t right:"+p.getRt());
				
				p=p.getLt();
			}
		}
		else
			System.out.println("stack::"+stack);
		
		
		if(top!=null)
			System.out.println("top::"+top.getData());
		else
			System.out.println("top::"+top);
	}
	public void linkInvrsionTraversal()
	{
		Node <  T  &rt;    cur=root;
		Node <  T  &rt;    		empty=root;
		Node <  T  &rt;    		prev=null;
		Node <  T  &rt;    		next=null;
		System.out.println("link inversal traversal::");
		do
		{
			while(cur!=null)
			{
				visit(cur);
				cur.setTag(0);
				next= cur.getLt();
//						cur-  &rt;   left=prev;
				cur.setLt(prev);
				prev=cur;
				cur=next;
			}
			next=cur;
			cur=prev;
			if(prev.getTag()==0)
				prev=prev.getLt();
			else
				prev=prev.getRt();
			cur.setLt(next);
			boolean up=true;
			do
			{
				if(cur.getRt()!=null && cur.getTag()==0)
				{
					cur.setTag(1);
					next=cur.getRt();
					cur.setRt(prev);
					prev=cur;
					cur=next;

					up=false;
				}
				if(cur.equals(empty))
				{
					cur.setTag(0);
					return;
				}
				if(up==true&&prev!=null)
				{
					Node <  T  &rt;    next_prev=null;
					
					
					if(prev.getTag()==0)
						next_prev=prev.getLt();
					else 
						next_prev=prev.getRt();
					
					if(prev!=null&&prev.getTag()==0)
					{
						cur.setTag(0);
						prev.setLt(cur);
						cur=prev;
						prev=next_prev;
					}
					else
					{
						
						cur.setTag(0);
						prev.setRt(cur);
						cur=prev;
						prev=next_prev;
					}

				}
				
			}while(cur!=null&&up);
			
		}while(cur!=null);
	}
	
	
	
	/**
	Write and test a "modified" Robson Traversal program that uses the linked representation of the trees. This modified version differs from the Robson only in that        the pointers to a node's predecessor should now be as in the Linked Inversion Traversal. That is, when a node's left(right) subtree is being traversed, its left(	  right) pointer will point to its predecessor. During the traversal, when a node is visited, output for each "stack' entry, its info value and the info value of i	   ts left and right successors. This means, first, output the number of the node Top points to, and then the number that that node's left and right pointers point 	    to. Then, output the number of the node that Stack points to,and then the numbers that that node's left and right pointers point to. Do this for each node on the	      "stack". Also, output similar information for each node along the path from the predecessor of the node being visited to the root. That is, for each of these no	      des output its info value and the numbers that the nodes left left and right pointers point to.
	*/
	public void modifiedRobsonTreeTraversal()
	{
		Node <  T  &rt;    cur=root;
		boolean rootHasOnlyRightChild=false;
		if(root!=null)
			rootHasOnlyRightChild=(root.getLt()==null)?(root.getRt()!=null?true:false):false;
		Node <  T  &rt;    		empty=root;
		Node <  T  &rt;    		prev=null;
		Node <  T  &rt;    		next=null;
		Node <  T  &rt;   			avail=null;
		Node <  T  &rt;            stack=null;
		Node <  T  &rt;            top=null;
		boolean done=false;
		System.out.println("\n===============================");
		System.out.println("Modified Robson traversal::");
		System.out.println("===============================");
		if(cur==null)
		{
			System.out.println("Sorry! it is a null tree");
			return;
		}
		do
		{
			while(cur!=null)
			{
				visit(cur,stack,top);
				next= cur.getLt();
				
				if(cur.getLt()==null&&cur.getRt()==null)
				{
					if(avail==null)
						avail=cur;
					else
					{
						cur.setRt(avail);
						avail=cur;
					}
				}
				cur.setLt(prev);
				prev=cur;
				cur=next;
			}
			next=cur;
			cur=prev;
			prev=prev.getLt();
			cur.setLt(next);
			boolean up=true;
			boolean leftTraversingFinished=true;
			do
			{
				if(cur.getRt()!=null&&cur!=avail&&leftTraversingFinished)
				{
					next=cur.getRt();
					cur.setRt(prev);
					if(cur.getLt()!=null)
					{

						if(top!=null)
						{
							Node <  T  &rt;    temp=avail;
							avail=avail.getRt();
							temp.setLt(null);
							temp.setRt(null);
							temp.setRt(top);
							if(stack==null)
								stack=temp;
							else
							{
								temp.setLt(stack);
								stack=temp;
							}
							
						}
						top=cur;
						
					}
					prev=cur;
					cur=next;
					up=false;
				}
				if(cur.equals(empty))
				{
					done=true;
				}
				if(up==true&&prev!=null)
				{
					Node <  T  &rt;    next_prev=null;
					boolean curIsPrevLeftChild=true;
					if(prev==empty)
					{
						next_prev=null;
						if(rootHasOnlyRightChild)
							curIsPrevLeftChild=false;
					}
					else if(prev.getLt()!=null&&top!=prev)
						next_prev=prev.getLt();
						
					else
					{
						next_prev=prev.getRt();
						curIsPrevLeftChild=false;
					}

					
					if(top==prev)
					{
						prev.setRt(cur);
						leftTraversingFinished=false;
						if(top!=null)
						{
							
							if(stack!=null)
							{
								top=stack.getRt();
								Node <  T  &rt;    currentStack=stack;
								stack=stack.getLt();
								currentStack.setLt(null);
								currentStack.setRt(null);
							}
							else 
								top=null;
						
						}
					
					}
						
					else if(curIsPrevLeftChild)
					{
						prev.setLt(cur);
						leftTraversingFinished=true;
					}
					else 
					{
						prev.setRt(cur);
						prev.setLt(null);
						leftTraversingFinished=false;
						
						
					}
					cur=prev;
					prev=next_prev;
				}
				
			}while(cur!=null&&up&&!done);
			
		}while(cur!=null&&!done);
		while(avail!=null)
		{
			Node <  T  &rt;    temp=avail;
			avail=avail.getRt();
			temp.setLt(null);
			temp.setRt(null);
		}
	}
}


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!