Hell can you help me on this,how can i insert a new node in the binary tree and to keep track the current node


example:

input number: 50

Succesfully inserted!

input number:40

this will print "inserted at the left of 50"

input numbr: 80

this will print "inserted at the right of 50"

input number: 20

this should print "inserted at the left of 40"

and etc.....

that is my problem how can i get track of the current node so that i can insert the new node,my code is always display the right of 50 or left of 50 it should follow th BST rule.....can you help me please thank you in advance hoping for your positive responds...

here is my code....

class Node
{
	public int num;
	public Node llink;
	public Node rlink;
	
}


public class BinaryTreeOperations
{
    private Node current;
    private Node root;
    private Node temp;
     
  public boolean isEmpty()
	{
		 return root==null;
	}
	
	
	public void insertNum(int n)
	{
	
	  Node temp=null;
	  Node current =null;
	
		
		Node newNode = new Node();
		newNode.num=n;
		newNode.llink=null;
		newNode.rlink=null;
		
		
		if(isEmpty())
		{
			root=newNode;
			System.out.println("Successfully inserted!");
		
		}
		
		else
		{
			temp=root;
			while(temp!=null)
			{
	           newNode = temp;
	           current = newNode;
	           temp =null;
			}
			
		if(n<current.num)
		{
			newNode.llink=newNode;
			current= newNode.llink;
	
			System.out.println("inserted on the left subtree ");
		}		
		 else
		 {
		 	newNode.rlink=newNode;	
		 	current = newNode.rlink;
	
			System.out.println("inserted on the right subtree  ");
		 }
		
		}
	}	
		
	public static void main(String args[])
	{
		
		Scanner console = new Scanner(System.in);
		
		BinaryTreeOperations bt = new BinaryTreeOperations();
		
        
   do{
   
	    		
	System.out.print("Insert a number: ");
	bt.insertNum(console.nextInt());
		        
	
	
   }
   while(select!=5);		
			
		
  }	
		
}

This happens because you don't "search" for the appropriate parent node for the new node to be inserted. You'd need a solution which recursively or within a loop searches for an appropriate parent to whose left/right the new node would be inserted. Read the basic algorithm here.

This happens because you don't "search" for the appropriate parent node for the new node to be inserted. You'd need a solution which recursively or within a loop searches for an appropriate parent to whose left/right the new node would be inserted. Read the basic algorithm here.

sir thank you for the reply,but the code that i have posted which has the while loop,if else...it's the pseudocode that my teacher give...

sir i have question the variable temp is that my parent?or my current variable?...sir help me i am confuse with the binary tree...i am new with this binary tree....i hope i can learn from you....Thank you in advance hoping for your positive
response...

This happens because you don't "search" for the appropriate parent node for the new node to be inserted. You'd need a solution which recursively or within a loop searches for an appropriate parent to whose left/right the new node would be inserted. Read the basic algorithm here.

Sir please help me i got error in my my code..

public void insertNum(int n)
	{
	
	    Node temp=null;
	    Node current=null;  
        
		
		Node newNode = new Node();
		newNode.num=n;
		newNode.llink=null;
		newNode.rlink=null;
		
		
		if(isEmpty())
		{
			root=newNode;
			System.out.println("Successfully inserted!");
		
		}
		
		else
		{
			temp=root;
			while(temp!=null)
			{
			  if(newNode<current.num)//i got error here!
			  { 
			  	 if(current.llink!=null)
			  	 	{
			  	 	  current=newNode.llink;
			  	 	  root=current;
			  	 	}
			  	 	
			  	 	
			  	 else
			  	 {
			  	 	root = newNode;
			  	 }
			  }	 	  	
			  	
			  	
			  else
			  if(n<current.num)
				{
		    		newNode.llink.num=root.num;
					System.out.println("inserted on the left subtree " +newNode.rlink.num);
				}		
		 		else
		 		{
		 			newNode.rlink.num=root.num;	
					System.out.println("inserted on the right subtree  "+newNode.llink.num );
		 		}
			}
		}
	}

please correct my code sir...thank you in advance hoping for yours positive response...

The error is because "newNode" is of type "Node" whereas "current.num" is an "int".

Also in your "insert()" code a few comments:

  • No need to explicitly set llink and rlink as NULL, they would anyways be NULL
  • If the tree is empty, insert the root node and return from the method
  • If the value of the newly inserted element is the same as the current node which is checked (temp), return again.
  • Also, you need to "re-assign" temp in your while loop so that you are always dealing with the appropriate node rather than always the root node.

Update your code and re-post again if it still doesn't work.

The error is because "newNode" is of type "Node" whereas "current.num" is an "int".

Also in your "insert()" code a few comments:

  • No need to explicitly set llink and rlink as NULL, they would anyways be NULL
  • If the tree is empty, insert the root node and return from the method
  • If the value of the newly inserted element is the same as the current node which is checked (temp), return again.
  • Also, you need to "re-assign" temp in your while loop so that you are always dealing with the appropriate node rather than always the root node.

Update your code and re-post again if it still doesn't work.

Hello sir thank you for the reply....sir i already edit my code but it still i get infinite loop..please help me sir Thank you in advance hoping for your positive response...

public void insertNum(int n)
	{
	
	    Node temp=null;
	    Node current=null;  
        
		
		Node newNode = new Node();
		newNode.num=n;
		//newNode.llink=null;
		//newNode.rlink=null;
		
		
		if(isEmpty())
		{
			root=newNode;
			System.out.println("Successfully inserted!");
		
		}
		
		else
		{
			temp=root;
			while(temp!=null)
			{
			  if(n<temp.num)
			  { 
			  	 if(temp.llink!=null)
			  	 	{
			  	 	  current=temp.llink;
			  	 	
			  	 	}	
			  	 else
			  	 {
			  	    current=newNode;
			  	 }
			  }	 	  	
			  	
			  else{
			  	current.rlink = temp;
			  }	
	
			  if(n<current.num)
				{
		    		current.llink.num=newNode.num;
					System.out.println("inserted on the left subtree " );
				}		
		 		else
		 		{
		 			current.rlink.num=newNode.num;
					System.out.println("inserted on the right subtree  " );
		 		}
			}
		}
	}

You still are not following the steps 2 to 4 as mentioned in my previous post; read and understand them and get back if it still isn't clear.

The infinite loop is because you check "temp" for NULL and since "temp" is not re-assigned in the while loop, the while loop never breaks.

You still are not following the steps 2 to 4 as mentioned in my previous post; read and understand them and get back if it still isn't clear.

The infinite loop is because you check "temp" for NULL and since "temp" is not re-assigned in the while loop, the while loop never breaks.

sir thank you for the reply but i could not still get clear in your instruction the step 2
i could not understand return to the method?...please help me sir thank you in advance hoping for your positive response....

You still are not following the steps 2 to 4 as mentioned in my previous post; read and understand them and get back if it still isn't clear.

The infinite loop is because you check "temp" for NULL and since "temp" is not re-assigned in the while loop, the while loop never breaks.

sir i am confuse what variable should i re-assign my temp?...thank you in advance hoping for your positive response....

The error is because "newNode" is of type "Node" whereas "current.num" is an "int".

Also in your "insert()" code a few comments:

  • No need to explicitly set llink and rlink as NULL, they would anyways be NULL
  • If the tree is empty, insert the root node and return from the method
  • If the value of the newly inserted element is the same as the current node which is checked (temp), return again.
  • Also, you need to "re-assign" temp in your while loop so that you are always dealing with the appropriate node rather than always the root node.

Update your code and re-post again if it still doesn't work.

Good Morning sir,

in this, If the tree is empty, insert the root node and return from the method

is this what you mean sir inserting the newNode to the root?please help me sir i am confuse....

if(isEmpty())
		{
			root=newNode;
			System.out.println("Successfully inserted!");
		}

sir i am confuse what variable should i re-assign my temp?

Reassign in the sense that since you want to continue traversing the tree and the "while" construct checks for the variable "temp", update temp accordingly based on the results of the comparison.

in this, If the tree is empty, insert the root node and return from the method

Just add a "return" statement after assigning a new node to the "root" so that you don't have to nest your remaining statements i.e. completely remove "else".

BTW, do you have an algorithm ready for this thing? This type of confusion normally happens when you don't completely understand what you are trying to implement. Write down the algorithm here which you are currently using to implement this binary tree.

Reassign in the sense that since you want to continue traversing the tree and the "while" construct checks for the variable "temp", update temp accordingly based on the results of the comparison.


Just add a "return" statement after assigning a new node to the "root" so that you don't have to nest your remaining statements i.e. completely remove "else".

BTW, do you have an algorithm ready for this thing? This type of confusion normally happens when you don't completely understand what you are trying to implement. Write down the algorithm here which you are currently using to implement this binary tree.

Hello sir thank you for the reply...but sir how can i put return my insertnum method is void?....

this is what i make last night,i can't get the current of my right root node...i will try your code sir also i will try my best to understand what you mean...but can you correct me in this code sir?is this wrong?


I am confuse also with my algorithm it is poor algorithm sir...i apologize i cant write my algorithm i just want to learn in this sir...Please help me sir Thank you in advance hoping for your positive response...

Node root;
     
     public boolean isEmpty()
     {
     	return root==null;
     }
       
      public void insertNum(int n)
      {
  
      Node temp=null;
      Node current=null;
   
      Node newNode = new Node();
      newNode.num=n;
 
 
      if(isEmpty())
      {
  
		root=newNode;
		System.out.println("Successfully inserted!");

      }
  
      else
      {
  
      temp=root;
      while(temp!=null)
      {
      
      	
      	if(n<temp.num)
      	{
      	
      		if(temp.llink!=null)
      		 {
      			current=temp.llink;
      			temp = current;
      		  }
             else
      		  {
      			current=temp;
      		
               } 
         
         
      	 }
          else
          {
          	if(temp.rlink!=null)
          	{
          		current=temp.rlink;
          		temp=current;
          	}
          	
          	else
          	  current = temp;	
          	
          }
          
         temp = temp.llink;
       
       }  
       	
  
		if(n<current.num)
		 {
			current.llink=newNode;
			System.out.println("inserted on the left subtree " + current.num);
		 }		
		 else
		 {
		 	current.rlink=newNode;	
			System.out.println("inserted on the right subtree  " +current.num);
		 }
		
		}
	  
      }

Hello sir thank you for the reply...but sir how can i put return my insertnum method is void?....

My point was that by doing early returns, you cut down the nesting depth. Also, just putting "return" is also valid and is in fact a well known method for breaking early.

if(isEmpty()) {
    root = newNode;
    System.out.println("Successfully inserted root node");
    return;
}
tmp = root;
while(tmp != null) {
    // remaining code
}

I am confuse also with my algorithm it is poor algorithm sir...i apologize i cant write my algorithm i just want to learn in this sir

I of course understand that and hence my suggestion to "write down the steps" so that you have the clarify of the implementation in your head before you go off to write the code. Anyways, you are almost there. You still don't handle the condition wherein a value is already present in the tree. Inside your "while", you need something like:

while(tmp != null) {
    if(tmp.num == n) {
        return; // value already present, break out
    }
    if(tmp.num < n) {
        // the new value should lie at the "RIGHT" of the current node
        // Is the right link for tmp NULL?
        //  if yes, then attach the new node to the right of tmp and print the message
        //  if no, then re-assign tmp as "tmp = tmp.rlink" and "continue"
    } else {
        // similar to above explanation; just replace "RIGHT" with "LEFT"
    }
}

Another point; why do you have "temp = temp.llink;" outside your "while" loop? Also, what is the point of having "if..else" outside the while loop?

My point was that by doing early returns, you cut down the nesting depth. Also, just putting "return" is also valid and is in fact a well known method for breaking early.

if(isEmpty()) {
    root = newNode;
    System.out.println("Successfully inserted root node");
    return;
}
tmp = root;
while(tmp != null) {
    // remaining code
}

I of course understand that and hence my suggestion to "write down the steps" so that you have the clarify of the implementation in your head before you go off to write the code. Anyways, you are almost there. You still don't handle the condition wherein a value is already present in the tree. Inside your "while", you need something like:

while(tmp != null) {
    if(tmp.num == n) {
        return; // value already present, break out
    }
    if(tmp.num < n) {
        // the new value should lie at the "RIGHT" of the current node
        // Is the right link for tmp NULL?
        //  if yes, then attach the new node to the right of tmp and print the message
        //  if no, then re-assign tmp as "tmp = tmp.rlink" and "continue"
    } else {
        // similar to above explanation; just replace "RIGHT" with "LEFT"
    }
}

Another point; why do you have "temp = temp.llink;" outside your "while" loop? Also, what is the point of having "if..else" outside the while loop?

Hello sir thank you so much for this i will try this and i will write again as soon as i can...more power to you....

My point was that by doing early returns, you cut down the nesting depth. Also, just putting "return" is also valid and is in fact a well known method for breaking early.

if(isEmpty()) {
    root = newNode;
    System.out.println("Successfully inserted root node");
    return;
}
tmp = root;
while(tmp != null) {
    // remaining code
}

I of course understand that and hence my suggestion to "write down the steps" so that you have the clarify of the implementation in your head before you go off to write the code. Anyways, you are almost there. You still don't handle the condition wherein a value is already present in the tree. Inside your "while", you need something like:

while(tmp != null) {
    if(tmp.num == n) {
        return; // value already present, break out
    }
    if(tmp.num < n) {
        // the new value should lie at the "RIGHT" of the current node
        // Is the right link for tmp NULL?
        //  if yes, then attach the new node to the right of tmp and print the message
        //  if no, then re-assign tmp as "tmp = tmp.rlink" and "continue"
    } else {
        // similar to above explanation; just replace "RIGHT" with "LEFT"
    }
}

Another point; why do you have "temp = temp.llink;" outside your "while" loop? Also, what is the point of having "if..else" outside the while loop?

Good Morning sir,

I follow your post sir but i have confussion in this
// the new value should lie at the "RIGHT" of the current node

that why i get null pointer.please help sir.Thank you in advance hoping for your positive response...here is my code sir
.....

private Node root;
     
     public boolean isEmpty()
     {
    	return root==null;
     }
       
      public void insertNum(int n)
      {
  
      Node temp=null;
      Node current=null;
   
      Node newNode = new Node();
      newNode.num=n;
 
 
      if(isEmpty())
      {
  
		root=newNode;
		System.out.println("Successfully inserted!");
	    return;

      }
  
    
     
  
      temp=root;
      while(temp!=null)
      {
        if(temp.num==n)
        {
          return;	
        }
      	
      	if(temp.num<n)
      	{
          current= temp;
           current.rlink.num=n;
      	
		
			if(temp.rlink==null)
			 {
			  temp.rlink.num=n;
			  System.out.println("Inserted at the right"+current.rlink.num);
			 }
			 else
			  {
			   temp=temp.rlink;
			  }
      	}
		
		else
		{
			
		     current=temp;
		     current.llink.num=n;
			
		   	if(temp.llink==null)
			 {
			  temp.llink=newNode;
			  System.out.println("Inserted at the left"+current.llink.num);
			 }
			 else
			  {
			   temp=temp.llink;
			  }			
		}
          } 
      }

When posting exceptions, make sure you include the full stack trace along with the "Line" on which the exception has occurred.

Anyways, I have highlighted the problematic part of the posted code:

if(temp.num<n)
      	{
          current= temp;
           current.rlink.num=n;
      	
		
			if(temp.rlink==null)
			 {
			  temp.rlink.num=n;
			  System.out.println("Inserted at the right"+current.rlink.num);
			 }

My comments:

  • current.rlink.num=n; : This part of code makes the assumption that the "current node" always has a right link which is non-null; this assumption is flawed. You don't even need this statement.
  • temp.rlink.num=n; : Again, this code is flawed since this piece is placed inside the IF check if(tmp.rlink == null) and hence will *always* cause NullPointerException.

When I say insert the value, you need to assign the "Node" object to rlink/llink instead of playing around with the "num" field. Like:

if(tmp.num < n) {
    if(tmp.rlink == null) {
        tmp.rlink = newNode;
    } else {
        tmp = tmp.rlink;
    }
}

When posting exceptions, make sure you include the full stack trace along with the "Line" on which the exception has occurred.

Anyways, I have highlighted the problematic part of the posted code:

if(temp.num<n)
      	{
          current= temp;
           current.rlink.num=n;
      	
		
			if(temp.rlink==null)
			 {
			  temp.rlink.num=n;
			  System.out.println("Inserted at the right"+current.rlink.num);
			 }

My comments:

  • current.rlink.num=n; : This part of code makes the assumption that the "current node" always has a right link which is non-null; this assumption is flawed. You don't even need this statement.
  • temp.rlink.num=n; : Again, this code is flawed since this piece is placed inside the IF check if(tmp.rlink == null) and hence will *always* cause NullPointerException.

When I say insert the value, you need to assign the "Node" object to rlink/llink instead of playing around with the "num" field. Like:

if(tmp.num < n) {
    if(tmp.rlink == null) {
        tmp.rlink = newNode;
    } else {
        tmp = tmp.rlink;
    }
}

Hello sir I think i got it i followed your comment....please correct me if i am wrong
Thank you in advance hoping for your positive response...sir if this is correct how can i get the height of the tree and the leaves and level of the tree...like i send you a while the problem

private Node root;
     
     public boolean isEmpty()
     {
    	return root==null;
     }
       
      public void insertNum(int n)
      {
  
      Node temp=null;
      Node current=null;
   
      Node newNode = new Node();
      newNode.num=n;
 
 
      if(isEmpty())
      {
  
		root=newNode;
		System.out.println("Successfully inserted!");
	    return;

      }
  
    
     
  
      temp=root;
      while(temp!=null)
      {
        if(temp.num==n)
        {
          return;	
        }
      	
      	if(temp.num<n)
      	{
          current= temp;
          //current.rlink=newNode;
      	
		
			if(temp.rlink==null)
			 {
			  temp.rlink=newNode;
			  System.out.println("Inserted at the right= "+current.num);
			 }
			 else
			  {
			   temp=temp.rlink;
			  // System.out.println("Inserted at the right" + current.num);
			  }
      	}
		
		else
		{
			
		     current=temp;
			 //current.=newNode;
			
			
		   	if(temp.llink==null)
			 {
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			  }		
		}
      }

Thank you in advance hoping for your positive response...sir if this is correct how can i get the height of the tree and the leaves and level of the tree...like i send you a while the problem

Post what you've got till now (regarding the tree height) and we'll pick it from there.

Post what you've got till now (regarding the tree height) and we'll pick it from there.

Hello sir,But sir i have no idea how to get the height,leaves,level of the tree...i don't really know sir can you help me please sir?

Post what you've got till now (regarding the tree height) and we'll pick it from there.

hello sir Please help me in getting the height here is my code i put variable,rcount,lcount.but i got errror

private Node root;
     int rcount=0;
     int lcount=0;
     
     public boolean isEmpty()
     {
    	return root==null;
     }
       
      public void insertNum(int n)
      {
  
      Node temp=null;
      Node current=null;
   
      Node newNode = new Node();
      newNode.num=n;
 
 
      if(isEmpty())
      {
  
		root=newNode;
		System.out.println("Successfully inserted!");
	    return;

      }
  
    
  
      temp=root;
      while(temp!=null)
      {
        if(temp.num==n)
        {
          return;	
        }
      	
      	if(temp.num<n)
      	{
          current=temp;
          
			if(temp.rlink==null)
			 {
			  temp.rlink=newNode;
			  System.out.println("Inserted at the right= "+current.num);
			 }
			 else
			  {
			   temp=temp.rlink;
			   rcount++;
			  }
      	}
		
		else
		{
			
		     current=temp;
			 	
			
		   	if(temp.llink==null)
			 {
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			 {
			   temp=temp.llink;
			   lcount++;
			  }	
				
		 }
		
      } 
       
   
      }


//in main
   
      case 2:
		    	
		    	 if(bt.rcount>bt.lcount)
	    	    	 System.out.println("The Height of the tree is: "+bt.rcount);    
	    	    	 else
	    	    	   System.out.println("The Height of the tree is: "+bt.lcount);  
	    	    break;

Post what you've got till now (regarding the tree height) and we'll pick it from there.

Sir thank you for helping me in this thread...it helps me a lot....more power to you...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.