problem in height in binary tree need help

Question

jemz -1 Master Poster

13 Years Ago

hello please help me how can i get the height of the tree?I really don't have idea how to get this can you help me please thank you in advance hoping for your positive response...here is my code

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;
			if(temp.rlink==null)
			 {
			  
			  temp.rlink=newNode;
			  System.out.println("Inserted at the right= "+current.num);
			 }
			 else
			  {
			   temp=temp.rlink;
			
			  }
      	}
		
		else
		{
			
		     current=temp;
		   	if(temp.llink==null)
			 {
				
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }

java

3 Contributors
13 Replies
186 Views
3 Days Discussion Span
Latest Post 13 Years Ago Latest Post by jemz

~s.o.s~ 2,560 Failure as a human

13 Years Ago

As per this, the basic algorithm for calculating the height of a binary tree is:

height(node): 
   if node == null:
        return 0
   else:
        max(height(node.L), height(node.R)) + 1

Now come up with an implementation and post your updated code if it still doesn't work.

~s.o.s~ 2,560 Failure as a human

13 Years Ago

Sir can i asked question max(height(node.L), height(node.R)) + 1 for what is this for just curious?

This expression inspects the heights of the left and right sub-tress (look at the recursive call "height") and returns the maximum of them. So basically, the first invocation of this method would be by passing in the "root" of the tree and this method would in turn invoke the same method for the nodes of the right/left subtree of the root node.

The best way here would be to "draw" a tree using pencil and paper and trace the output of the calls.

jon.kiparsky 326 Posting Virtuoso

13 Years Ago

max is a shorthand for "a function returning the maximum of two numbers". You'll find an implementation of such a function in java.Math.

~s.o.s~ 2,560 Failure as a human

13 Years Ago

What kind of error? Compile time? Run time? Post the latest code and highlight the line which gives the error along with the complete error description.

Reply to this topic

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.

jemz -1 Master Poster · Answer 1 · 2011-02-02T06:38:18+00:00

As per this, the basic algorithm for calculating the height of a binary tree is:
height(node): 
   if node == null:
        return 0
   else:
        max(height(node.L), height(node.R)) + 1
Now come up with an implementation and post your updated code if it still doesn't work.

Hello sir thank you for the reply....Sir can i asked question max(height(node.L), height(node.R)) + 1 for what is this for just curious?...Okay sir i will post my code as soon as possible...thank you in advance hoping for your positive response...more power to you...

jemz -1 Master Poster · Answer 2 · 2011-02-02T22:34:29+00:00

This expression inspects the heights of the left and right sub-tress (look at the recursive call "height") and returns the maximum of them. So basically, the first invocation of this method would be by passing in the "root" of the tree and this method would in turn invoke the same method for the nodes of the right/left subtree of the root node.
The best way here would be to "draw" a tree using pencil and paper and trace the output of the calls.

hello sir thank you for explaining it...BTW here is my code i implement the recursion?

but i get an error can't find symbol max...can you help me sir thank you in advance hoping for positiver response...

public int height(Node n)
     {
     	if (n==null)
     	   return -1;
     	   	else
     	   	 max(height(n.llink),height(n.rlink))+1;		
     	
     }   
        
     
   
       
      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;
			
			  }
      	}
		
		else
		{
			
		     current=temp;
		   	if(temp.llink==null)
			 {
				
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }

jemz -1 Master Poster · Answer 3 · 2011-02-03T06:00:18+00:00

max is a shorthand for "a function returning the maximum of two numbers". You'll find an implementation of such a function in java.Math.

hello sir thank you for the reply,sir why is that i got error on my method height?
I just follow the example @SOS but i get an error can you help me on this sir thank you in advance hoping for your positive response...BTW sir in the if Statement sir why is it -1 not 0?...thank you in advance hoping for your positive response...

jemz -1 Master Poster · Answer 4 · 2011-02-03T12:02:30+00:00

What kind of error? Compile time? Run time? Post the latest code and highlight the line which gives the error along with the complete error description.

Here's the error and my code sir

private Node root;
     private int count;

     
     public boolean isEmpty()
     {
    	return root==null;
     }
     
	  public int height(Node node)
	  {
	  		if (node == null)
        		return -1;
   			else
               max(height(node.llink), height(node.R)) + 1
	  	
	  }
   		

        
     
 
      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;
			
			  }
      	}
		
		else
		{
			
		     current=temp;
		   	if(temp.llink==null)
			 {
				
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }

here is the error please help me sir

D:\BinaryTreeOperations.java:29: not a statement
               max(height(node.llink), height(node.R)) + 1;

1 error

Process completed.

jemz -1 Master Poster · Answer 5 · 2011-02-03T12:49:08+00:00

What kind of error? Compile time? Run time? Post the latest code and highlight the line which gives the error along with the complete error description.

sir i apologize please disregard the first post i forgot to change the method here is my final code sir...but same error...

private Node root;
     public boolean isEmpty()
     {
    	return root==null;
     }
     
	  public int height(Node node)
	  {
	  		if (node == null)
        		return -1;
   			else
               max(height(node.llink), height(node.rlink)) + 1;
	  	
	  }
   		
      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;
			
			  }
      	}
		
		else
		{
			
		     current=temp;
		   	if(temp.llink==null)
			 {
				
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }


here is the error sir

D:\BinaryTree.java:29: not a statement
               max(height(node.llink), height(node.rlink)) + 1;

Please help me sir Hoping for your positive response...

~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster · Answer 6 · 2011-02-03T13:55:21+00:00

That's because you ignored Jon's reply:

max is a shorthand for "a function returning the maximum of two numbers". You'll find an implementation of such a function in java.Math.

Also, when the node is NULL, don't return -1 but 0 if you want the height of a single node tree to be 1.

jemz -1 Master Poster · Answer 7 · 2011-02-04T21:24:34+00:00

That's because you ignored Jon's reply:
Also, when the node is NULL, don't return -1 but 0 if you want the height of a single node tree to be 1.

Hello sir thank you for the reply is this what Jon's mean?Please correct me if i am wrong...Thank you in advance hoping for your positive response...

private Node root;
     private int count;
  
     
     public boolean isEmpty()
     {
    	return root==null;
     }
     
        
        
     public int height(Node n)
     {
     	if (n==null)
     	   return 0;
     	   	else
     	   return Math.max(height(n.llink),height(n.rlink))+1;		
     	
     }   
        
     
   
       
      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;
			
			  }
      	}
		
		else
		{
			
		     current=temp;
		   	if(temp.llink==null)
			 {
				
			  temp.llink=newNode;
			  System.out.println("Inserted at the left= "+current.num);
			 }
			 else
			  {
			   temp=temp.llink;
			 
			  
			  }	
				
                 }
		
           } 
      }

~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster · Answer 8 · 2011-02-04T21:40:25+00:00

What do you think? Are you still getting compile time errors? Have you tried running it with a sample tree? Does it give out correct values? Wrong values?

jemz -1 Master Poster · Answer 9 · 2011-02-05T04:04:56+00:00

What do you think? Are you still getting compile time errors? Have you tried running it with a sample tree? Does it give out correct values? Wrong values?

hello sir yes there is no compile error and it gives me the correct value,Thank you so much sir and to Jon's...more power to you...please help me in my thread getting the leaf...thank you in advance hoping for your positive response...