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);
		}
	}
}


Discussion for Integer Overflow in Java

Standard

Today, I was reading an article for overflow and cannot stop myself from sharing the gist of it.

Let us discuss this solution of binary search tree.

public int binarySearchTree(int a[],int item)
{
  int start=0;
  int end=a.length-1;
  while(start<=end)
  {
      int mid=(start+end)/2;
      if(a[mid]==item)
               return mid;
      else if(a[mid]<item)
               start=mid+1;
      else
                end=mid-1;
}
return -1;
}

 

if we carefully check these lines of code, we will realize that the line mid=(start+end)/2 may result in overflow, what if start+end > Integer.MAX_VALUE then mid will have a -ve value.  To overcome this sort of potential programming bug (this bug is still existing in Java’s Arrays Binary search and it has been earlier reported by Joshua Bloch) , it will be better to write this line of code as this,

1)  mid= start + (end-start)/2;
or
2) mid = (start+high) >>>1; //since in java “>>>” is unsigned right shift operator.
 
Now let us try to write a utility class to check whether different arithmetic operation is overflow safe or not.

For this let us start to discuss which all arithmetic operation can result in overflow, here I will like to point out that any logical operation like &, | and ^ cannot result in overflow thats why we are only discussing arithmetic operation.

1) Addition:  a+ b can result in overflow as we have seen in above discussion. So, we need to have a utility method for this.

2)  Subtraction: same like for addition it can also result in overflow.

3)  Multiplication: a*b, can easily result in overflow.

4) Division: consider this case Integer.MIN_VALUE/-1,  this will result in overflow.

5) Negation: – (Integer.MIN_VALUE) can result in overflow again.

 

Here is the Utility class has methods to check the safety for each of the above discussed arithemetic operations:-

package org.aakash.pratice;

public class OverflowCheckUtility {

public static boolean isSafeToSubtract(int i,int j)
{
    if(!isSafeToNegate(j))
          return (i&Integer.MIN_VALUE)<0;
    return isSafeToAdd(i, -j);
}
public static boolean isSafeToNegate(int i)
{
    return i!=Integer.MIN_VALUE;
}
public static boolean isSafeToAdd(int i,int j)
{
    int k=i+j;
    if(((i^k)&(j^k))<0)
         return false;
    return true;
}
public static boolean isSafeToDivide(int i,int j)
{
   if(i<=Integer.MAX_VALUE&j==-1)
      return false;
   return true;
}
public static boolean isSafeToMultiply(int i,int j)
{
   int k=i*j;
   boolean expectedSign=((i&Integer.MIN_VALUE)^(j&Integer.MIN_VALUE))>=0?true:false;
   boolean actualsign=(k&Integer.MIN_VALUE)>=0?true:false;
   return expectedSign==actualsign;
}
/**
   Testing utility class for different boundry values
* @param args
*/

public static void main(String[] args) {
// TODO Auto-generated method stub
     int count=0;
     int n=Integer.MIN_VALUE;
//        int n=-1;
    while(n!=0)
    {
        n=(n-1)&n;
        count++;
     }
     System.out.println(count);
     System.out.println(Integer.MAX_VALUE*2);
     System.out.println(Integer.MAX_VALUE*-2);
     System.out.println(Integer.MIN_VALUE*2);
     System.out.println(Integer.MIN_VALUE*-1);
     System.out.println("::checking for multiply");
     int i=-1;
     System.out.println(isSafeToMultiply(i, Integer.MIN_VALUE));
     System.out.println(isSafeToMultiply(i, Integer.MAX_VALUE));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/3));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE/2));
     System.out.println(isSafeToMultiply(2, Integer.MAX_VALUE));
     System.out.println(isSafeToMultiply(-2, Integer.MIN_VALUE/2));


     System.out.println("checking subtraction");
     System.out.println(isSafeToSubtract(-1, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE));
     System.out.println(isSafeToSubtract(1, Integer.MIN_VALUE));
     System.out.println(isSafeToSubtract(-12, Integer.MIN_VALUE));
     System.out.println(isSafeToSubtract(-1, Integer.MIN_VALUE));

     System.out.println("checking addition");
     System.out.println(isSafeToAdd(-1, Integer.MIN_VALUE));
//        System.out.println(isSafeToSubtract(-2, Integer.MAX_VALUE));
//        System.out.println(isSafeToSubtract(-5, Integer.MAX_VALUE));
//        System.out.println(isSafeToSubtract(1, Integer.MAX_VALUE));

}