Sunday, 16 July 2017

Binary tree in java. isdescendent() isfind() closestcommonancestor() getlevel() iscousin() totalvalue() numberofnodes()


public class BinTree
{
    BinTree left ;
    BinTree right;
    int value;
    public BinTree(int m)
    {
        left= null;
        right= null;
        this.value= m;
    }
    public static void main(String[] args)
    {
        BinTree root = new BinTree(1);
        root.left = new BinTree(2);
        root.right = new BinTree(3);
        root.left.left= new BinTree(4);
        root.left.right = new BinTree(6);
        root.right.left = new BinTree(5);       
        root.right.right = new BinTree(7);
        //boolean y= root.find(2);
        /*System.out.println(y);
        System.out.println(root.numberOfNodes());
        System.out.println(root.totalValue());
        System.out.println(root.isDescendent(7,3));
        System.out.println(root.isSibling(7,5));
        System.out.println(root.isCousin(2,7));    */
        System.out.println(root.closestCommonAncestor(6,2).value);
}

     boolean find(int m)
    {
                   
                   
            if (this.value==m)
            {
                //System.out.println(this.value);
                    return true;

            }
            else
            {
                boolean l_result=false,r_result=false;               
                if (this.left !=null)               
                { l_result = this.left.find(m);}
                if (this.right !=null)               
                {r_result = this.right.find(m);}               
                return (l_result|r_result);
            }
                   
    }
       
    int numberOfNodes()
    {   
        {
             int size_l=0,size_r=0;
            if (this.left != null)
            {
                size_l = this.left.numberOfNodes();
            }
            if(this.right !=null)
            {
                size_r= this.right.numberOfNodes();
            }
            return size_l+size_r+ 1;
        }
    }
   
    int totalValue()
    {   
        {
             int value_l=0,value_r=0;
            if (this.left != null)
            {
                value_l = this.left.totalValue();
            }
            if(this.right !=null)
            {
                value_r= this.right.totalValue();
            }
            return value_l+value_r+ this.value;
        }
    }
   
   
     BinTree find2(int m)
    {
                   
             BinTree x = null;           
            if (this.value==m)
            {
                System.out.println(this.value);
                 x = this ;
                return x;
               

            }
            else
            {               
                if (this.left !=null)               
                { x=this.left.find2(m);}
                if (x== null)
                {               
                    if (this.right !=null )               
                        {x=this.right.find2(m);}
                }               
               
            }

            return x;
                   
    }
   
    boolean isDescendent(int x, int y) //check whether x is decendent of y
    {
        BinTree m= this.find2(y);
        if (m== null)
        {
            System.out.println("ancestor not found");
        }       
        return m.find(x);
       
    }                       
   
    boolean isSibling(int m, int n)
    {
        if( (this.left!=null)& (this.right!=null) )       
        {    if ((this.left.value == m & this.right.value == n)| (this.left.value ==n & this.right.value ==m))
            return true;
            else
            {
                boolean l_result=false,r_result=false;               
                    if (this.left !=null)            
                    { l_result = this.left.isSibling(m,n);}
                    if (this.right !=null)            
                    {r_result = this.right.isSibling(m,n);}               
                    return (l_result|r_result);
            }                   
        }
        return false;   
    }
    boolean isCousin(int m , int n)
    {
        int l_1= this.getLevel(m);
        System.out.println(l_1);
        int l_2 =this.getLevel(n);
        System.out.println(l_2);
        if(l_1==l_2)
        {
            return true;
        }   
        else
            {return false ;}
    }
    int getLevel(int m)
    {    
        if (this.value==m)
        {
            return 1 ;
        }
        else
        {           
            int level=0;           
            if(this.left!= null)
            level= this.left.getLevel(m);
            if (level!=1)
            {
                {if (this.right!=null)
                level =this.right.getLevel(m);       
                }
            }
            if (level==0)
            {
                return 0;
            }
            else
            {
                return level+1;
            }
        }
    }

    BinTree closestCommonAncestor(int m, int n)
    {
        if( this.left!= null & this.right!=null)
        {
            boolean b= false;
            boolean a = false ;
             a= this.left.find(m)  | this.value==m;
            if (a == true)
            { b = this.right.find(n)| this.value==m;}
           
            else
            {
                 a= this.right.find(m);
                if (a == true)
                {
                    b= this.left.find(n)| this.value==n;       
                }
            }               
            if (a & b)
            {
            return this;
            }
       
            else {
                BinTree x= null;
                if (this.left!= null)
                       
                    {
                        x= this.left.closestCommonAncestor(m,n) ;}
                if (x ==null)
                {   
                    if (this.right!= null)
                    {   
                        x = this.right.closestCommonAncestor(m,n) ;}
                 }
                return x;
            }
       
        }return null;
    }   
}

No comments:

Post a Comment