Insert numbers in a binary search tree

[rebps arora]

Hi I am trying to make binary search tree...I am trying to construct the left part of binary search tree with root node set as 70...It is not working ...Can someone please make changes in code so that it works fine...My code is
public class Node {

/**
* @param args
*/

int root;
Node left;
Node right;

public void insertNode(Node node, int num) {
//Node nodeRoot = this;
//root of tree we have set to 70...constructing only left of tree with root=70

if(num<node.root)
{
while(node.left!=null)
{
node=node.left;
//suppose we insert 56 that goes to left of 70 but after that we insert 60
if(num>node.root)
{
Node temp = new Node();
temp.root = num;
node.right = temp;

System.out.println(num + "" + "at right of" +node.root);

}


}
//some condition is required here.....
Node temp = new Node();
temp.root = num;
node.left = temp;
System.out.println(num + "" + "at left of" +node.root);


}







public static void main(String[] args) {
// TODO Auto-generated method stub

Node node = new Node();

node.root=70;
System.out.println("building tree with" + "" + node.root);
// node = node.insert(node, 70);
node.insertNode(node, 56);
/* node.insertNode(node, 45);
node.insertNode(node, 15);
node.insertNode(node, 16);
node.insertNode(node, 60);
node.insertNode(node, 80);
node.insertNode(node, 85);*/
/*node.insertNode(node, 45);
node.insertNode(node, 56);
node.insertNode(node, 16);
node.insertNode(node, 15);
node.insertNode(node, 60);
node.insertNode(node, 80);
node.insertNode(node, 85);*/
}

}

[John Jai]

Hi Rebs,

Welcome to the Ranch

To get better help please TellTheDetails since ItDoesntWorkIsUseless

Can someone please make changes in code so that it works fine

I doubt any one will provide direct solution rather than help you find it... So please tell as what is your intention and where you are struck exactly.

I have added some Code Tags to your code and removed commented lines to make it look clearer.

public class Node {
	
	int root; 
	Node left; 
	Node right; 

	public void insertNode(Node node, int num) { 
		if(num < node.root) 
		{ 
			while(node.left != null) 
			{ 
				node = node.left; 
				if( num > node.root) 
				{ 
					Node temp = new Node(); 
					temp.root = num; 
					node.right = temp; 
					System.out.println(num + "" + "at right of" +node.root); 
				} 
			} 
			Node temp = new Node(); 
			temp.root = num; 
			node.left = temp; 
			System.out.println(num + "" + "at left of" +node.root); 
		} 
	}


	public static void main(String[] args) { 
		Node node = new Node(); 
		node.root=70; 
		System.out.println("building tree with -> " + node.root); 
		node.insertNode(node, 56); 	
	} 

} 

[rebps arora]

Hi John,

What i expect is:

If i call
node.insertNode(node, 56);
node.insertNode(node, 59);
node.insertNode(node, 45);
node.insertNode(node, 43);

The output should be:

56 at left of 70
59 at right of 56
45 at left of 56
43 at left of 45

[Campbell Ritchie]

I prefer the recursive approach

/**
 * Pseudo-code which can be changed.
 * You may, for example, return true/false depending on whether a value has been added.
 * You may change the structure to support duplicates.
 */
add method:
if newValue < value
   if left is null
      left becomes new node with newValue as value
   else
      call add method on left with newValue
else if newValue > value
   if right is null
      right becomes new node with newValue as value
   else
      call add method on right with newValue
[No else here: this is a set, so duplicates are simply discarded.]

[rebps arora]

Hi Campbell/John

Can you please help me in doing the same by non recursive method.

public class Node {   
       
    int root;    
    Node left;    
    Node right;    
  
    public void insertNode(Node node, int num) {    
        if(num < node.root)    
        {    
            while(node!= null)    
            {    
                node = node.left;    
                if( num > node.root)    
                {    
                    Node temp = new Node();    
                    temp.root = num;    
                    node.right = temp;    
                    System.out.println(num + "" + "at right of" +node.root);    
                }    
            }    
            Node temp = new Node();    
            temp.root = num;    
            node.left = temp;    
            System.out.println(num + "" + "at left of" +node.root);    
        }    
    }   
  
  
    public static void main(String[] args) {    
        Node node = new Node();    
        node.root=70;    
        System.out.println("building tree with -> " + node.root);    
        node.insertNode(node, 56);     
    }    
  
}   

[John Jai]

If you don't want to use a recursive method, you have to use a flag to check whether the addition of the new node is done.

The steps might not be clear. Let me take a try though.

// Step 1 - Make a boolean variable so that the loop is iterated till the node is added
boolean isNodeAdded = false;

// Step 2 - use the boolean variable and iterate till the node gets added..
while (! isNodeAdded){
        
    // Step 3 - Read the root value of the passed node
	int nodeRoot = node.root;

    // Step 4 - Check if the node is already been added... This check will run every time the loop executes...
	if(nodeRoot == num){
		System.out.println("The node " + num + " is already added....");
		isNodeAdded = true;
	}

   // Step 5 - Check whether the number passed is less than the node's root value..
	else if(num < nodeRoot){
               
                // Step 5.1 Check whether there is already a node added to the left of the passed node
		if(node.left == null){
			// No node is added... So we are going add the given number to the node's left..

                        // Create a node and assign its root value to the passed number.

                        // Mark the newly created node as the passed node's left (using the instance variable left)

                        // Mark the passed node as the newly created node's right (using the instance variable right)

                        // Make the isNodeAdded boolean as true... So that the while loop terminates...			

		}
           // Step 5.2 - Already a node exists in the left of the passed node.
           else {
                   // Get the root value of the node that is left of the passed node...
		     int leftNodeRoot = node.left.root; 
                        
                   // Step 5.2.1 - Compare the already present left node's root with the given number...

                   // If the left node's root value is greater than the number then the loop has to be executed again...

                   // Means if the node passed is 70, the number passed is 56 and a node with value 60 is already present, 
                   // then 56 should be added to the left of 60...

                   // The loop is run again to check whether still 60 has something to its left... say 58... 
                   // then 56 should be added to 58's left and not 60's left :)

	           if(leftNodeRoot >= num){				
			          node = node.left;
                    // In the above line the reference of the node is made to point to 60 (or the node left to the passed node)
	            }
	            else {
                              
                           // Still Step 5.2.1 - Else part - The left node added is lesser than the given number... 
                           // that is 45 is added to the left of 70... and current passed number is 56
				
			          // Create a node and assign its root value to the passed number.
                                
                          // The new node (56) should be *inserted* between current node's left (45) and current node (70)

                          // Mark the newly created node as the current node's left node

                          // Mark the right of current node's left node (45) as the new node (56)

                          // Mark the current node's left node (45) as the left node of the new node (56)

                          // Mark the new node's right node (56) as the current node (70)
 
                          // Mark the boolean isNodeAdded variable as true... to enable loop termination...			

			     isNodeAdded = true;
		}
					
		}
	}
        // Step 6 - The number passed is greater than the passed node's root...
	else {
                // Reverse the steps you did when the number is lesser than the passed node's root value...		
		}
	}			
}

Note that you have to implement code when the number is greater than the passed node's root...