Find the logical error in the following code

Hi ,

The following code is meant for creating a binary search tree. But however because of the language semantics and the programmers oversight there are logical errors in the code. Try to find the errors if you can.. It takes good understanding of Java to find out the logical errors. All the very best ... 

class MyBinarySearchTreeNode {

    Integer value;
    MyBinarySearchTreeNode left;
    MyBinarySearchTreeNode right;
   
    public MyBinarySearchTreeNode() {
        // TODO Auto-generated constructor stub
        value=null;
        left=null;
        right=null;
       
    }
   
    public MyBinarySearchTreeNode(Integer value) {
        // TODO Auto-generated constructor stub
        this.value=value;
        left=null;
        right=null;
       
    }
   

}

******************************Another class in the same file **************************

public class MyBinarySearchTree{
   
    MyBinarySearchTreeNode rootNode;
   
    public MyBinarySearchTree(){
        rootNode=null;
    }
   
    public void insertNode(MyBinarySearchTreeNode node){
       
        /* check if root node is null
         *
         * if null then its the first node to be inserted .
         *
         * So make it the root the node.
         *
         * */
       
             
        if(rootNode==null){
           
              rootNode=node;
            rootNode.left=null;
            rootNode.right=null;

            return;
        }
       
        /*
         * if root node is not null then we need to traverse the
         *
         * tree to find the appropriate position.
         *
         */
       
        else {
           
                       
            MyBinarySearchTreeNode currNode;
            MyBinarySearchTreeNode nextNode;
           
           
            currNode=rootNode;
            nextNode=null;
           
          
            while(nextNode==null){
               
                             
                            if(node.value<currNode.value){
                                        if(currNode.left!=null){
                    currNode=currNode.left;
                    }
                    else{
                       
                       
                        nextNode=currNode.left;
                                            }
                }
                else if(node.value>currNode.value){
                                        if(currNode.right!=null){
                    currNode=currNode.right;
                    }
                    else{
                                           nextNode=currNode.right;
                                            }
                }
            }
           
                        nextNode=node;
           
           
           
           
        }
       
       
       
       
    }

public static void main(String args[]){
        MyBinarySearchTreeNode node=new MyBinarySearchTreeNode(11);
       
        MyBinarySearchTree btree=new MyBinarySearchTree();
       
        btree.insertNode(node);
       
        for(int i=0;i<10;i++){
           
            System.out.println("\n Enter value for next node");
           
            DataInputStream din=new DataInputStream(System.in);
            int val=0;
            try{
            val=Integer.parseInt(din.readLine());
            }
            catch(Exception e){
                System.out.println("Exception"+e.getMessage());
            }
            node.value=val;
            node.left=null;
            node.right=null;           
            btree.insertNode(node);
        }
       
            }
   
   
}

For clarity below is the description.

MYBinarySearchTreeNode is a class used for representing Nodes.

MyBinarySearchTree class is used for implementing the logic.

Furhter mail method is also written in Tree class.

Finally if you have identified the logical error(s) post it here in the comments section.

Some basics about Trees.

Binary Tree:

A binary tree is a finite set of elements that is either empty or divided into three disjoint sets namely

1.A set containing a single element called root node.
2.A left subtree( can be empty)
3.A right subtree.(can be empty)

So from the above definition , a tree is defined in terms of itself only , recursively.

In a nut shell we can say in a binary tree ea can have atmost two child for each node.Further more the term disjoint plays an important role in the definition of the binary tree. You infer why .

Note that there is no restrictions on the values of the right and left sub-tree in a tree. ( like all those values in left subtree must be less than or equal to root nodes value etc.. )

There are concepts like ancestor,descendant, father, brother etc.. which I am not going to discuss as ;they are analogous to the usual blood relationships and user an easily understand those concepts. Can take it as an excercise.

Before diving into the properties of Binary trees lets see some more definitions .

Level of a node in a binary tree is defined as follows:
1. Level of root node is 0.
2.Level of node n is level of node n's father +1.

Depth of a binary tree is the maximum level of any leaf node in the tree.


Now lets discuss some of the properties of the Binary trees:

Property : The maximum number of nodes at level  'i' in a binary tree is 2ⁱ

Proof:

Induction basis:

We know that the no of nodes at level 0 is 1. i.e root node.

So when n=0  2ⁿ =1

So true for n=0

Induction Hypothesis:

Lets consider that  no of nodes at level K is 2^k for some n=k.

Now we have to show that 2^k+1 is true for n=k+1.

From the inductin hypothesis we have 2^k node at level K. From the definition of binary tree each node can have atmost two children. Therefore at K+1 level , considering each node at level K can have amost two children,

no of nodes at level K+1 <=2^K *2
                                       <=2^K+1

Hence proved.



Property:

The maximum no of nodes in a binary tree of depth K is 2^K+1-1.

Proof:

from the above proof maximum no of nodes at level k is 2^k , at K-1 is 2^k-1 ....

total no of nodes is <=2^k+2^k-1+... +2⁰
                              <=2^k+1-1 ( By induction we can prove this )


 Property:

For any non-empty binary tree T, if n0 is the no. of leaf nodes & n2 is the no. of nodes of degree 2, then n0 = n2 + 1.

Proof:Let n be the total no. of nodes in binary tree.

            n0 no. of nodes of degree 0

            n1  no. of nodes of degree 1

            n2  no. of nodes of degree 2

                        n = n0 + n1 + n2  -----> (1)

            All the nodes except the root node has a branch coming into it. Let B be the no. of branches in the binary tree.

                        n = B + 1 ----->(2)

                        B = 0.n0 + 1 * n1 + 2*n2 since there would be 0 branches from n0, and 1 branch from n1 nodes and two branches from n2 nodes

                        B = n1 + 2n2    ---->3

            Substituting (3) in (2).

                        n =  n1 + 2n2 + 1  ----> 4.

            Equate 1 & 4

                        n0 + n1 + n2 = n1 + 2n2 + 1

                        n0 = n2 + 1

Proved.

Strictly Binary Tree:
If every non leaf node in a binary tree has non empty left and right sub trees, then the tree is termed as strictly binary tree.

So , from the definintion , it is evident that strictly binary tree contains nodes of degree 2 or 0 but not 1.

Property:

The strictly binary tree with n leaf nodes contains 2n-1 nodes.

Proof:

Let number of nodes in Strictly binary tree be N.

Then N=n0+n1+n2. where n0,n1 and n2 are no of nodes of degree 0,1 ad 2 respectively.

From the definition of Strictly binary tree n1=0. as there wont be any nodes of degree 1.

==> N=n0+n2.

From the property of binary trees n0=n2+1.

==> N=n0+n0-1

==> N=2n0-1

if we consider no of leaf nodes =n this implies n=n0.

therefore N=2n-1.

Hence proved.

Complete Binary tree or full Binary tree:

A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. That is in Complete binary tree only nodes of degree 2 or 0 exist . further more all leaves would be at the same level .

As we have seen , in a binary tree with depth d, the maximum possible no of nodes is pow(2,d+1)-1 ( proved above) the maximum case occurs when the binary tree is a complete binary tree.

So when given the depth of full binary tree we compute the no of nodes as pow(2,d+1)-1.

Given the no of nodes we can compute the depth as log(n+1) -1 in base 2.