Leaf problem in BinaryTre Need Help

Question

jemz -1 Master Poster

13 Years Ago

Hello can you help me please how can i get the leaf in the Binary Tree.I Dont have idea on the leaf?...can you help me please thank you in advance hoping for your positive response...

here is my code...

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
14 Replies
232 Views
4 Weeks Discussion Span
Latest Post 13 Years Ago Latest Post by jemz

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

13 Years Ago

As it has already been mentioned many times before, posting questions without showing attempt would be ignored by most members here. Also, a simple search for "find leaf node" would bring up the description of a leaf node with its implementation.

BTW, please don't PM me. I have limited time I can spare on this forum. Instead focus on framing the question in such a way which would yield maximum responses.

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

13 Years Ago

When posting error messages, post the entire exception stack trace by highlighting the line on which the error has occurred rather than just posting the exception message.

Also, why does left() method take a count? Is this method for counting leaf nodes? Returning all the values of leaf nodes?

You check for node.llink != null && node.rlink != null , but what happens if one of them is null and the other isn't? You still end up calling leaf() method which doesn't have a NULL check and hence the exception.

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

13 Years Ago

What's your end goal here? Printing out the values of the leaf nodes or returning them to the caller?

Also, since you have written almost all the code here, you need to come up with your own ways of verifying the correctness of your code rather than asking others to verify. A few test cases which I can come up with are:

Pass the root (which would be NULL) of an empty binary tree -> should print nothing
Pass a tree containing just a single node (i.e. the root) -> should print root value
Pass a tree created using the values (1, 2, 3, 4) -> output should be 4
Pass a tree created using the values (4, 3, 2, 1) -> output should be 1
Pass a tree created using the values (10, 3, 20, 1, 4, 15, 25) -> output should be (1, 4, 15, 25)

Give it a try!

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

13 Years Ago

Hello sir I am printing the values of my leaf nodes.

OK

I am just asking if i got the right way of getting the leaf values and if it is efficient i know you also have your own code in this which is more efficient...

Likewise, I'm implying that you don't need my help to confirm that your algorithm works. You can run the test cases I posted above (once through code and once by using pen n paper) to confirm the same. Also, assuming that this is for some university course, first concentrate on correctness, then on performance/speed.

Sir about the test above can you give me the example?so that i can have idea and work with it?Thank you in advance hoping for your positive response...

Example as in code? No. The entire purpose of giving the least possible information of my posts have to do with you learning how to start thinking the right way. Have you been implementing this code just based on the suggestions/algorithm posted? If not, I'm sure you can at least try rather than directly asking for assistance. How do you create a empty tree? How do you create a tree with a single node? How would you create a tree with 3 given numbers? Like I said previously, try it out, it shouldn't be that difficult.

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-08T13:10:05+00:00

As it has already been mentioned many times before, posting questions without showing attempt would be ignored by most members here. Also, a simple search for "find leaf node" would bring up the description of a leaf node with its implementation.
BTW, please don't PM me. I have limited time I can spare on this forum. Instead focus on framing the question in such a way which would yield maximum responses.

hello sir here is my code I hope you will help me please....my error is null pointer.Thank you in advance hoping for your positive response...

private Node root;
     private int count;
     private int leaf=0;
     
     public boolean isEmpty()
     {
    	return root==null;
     }
     
	  public int height(Node node)
	  {
	  		if (node == null)
        		return -1;
   			else
               return Math.max(height(node.llink), height(node.rlink)) + 1;
	  	
	  }
   		

        
      public void leaf(Node nd,int c)
      {
      	 int [] numleaves = new int[c];
      	
      	  if(nd.llink == null && nd.rlink == null)
      	 
      	     for(int i=0;i<c;i++)
      	     {
      	     	numleaves[i]=nd.num;
      	     	System.out.print(numleaves[i]+ " ");
      	     }
      	     	
      	 else
      	 	leaf(nd.llink,c);
      	 	leaf(nd.rlink,c);
      	
      }  
 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!");
		count++;
	    return;

      }
  
      
     
      temp=root;
      count++;
      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;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }
public static void main(String args[])
	{
		
		Scanner console = new Scanner(System.in);
		
		BinaryTree bt = new BinaryTree();
		
        	int select=0;
do
{

  switch(select)
	    {
	case 4:
	    		
	    		
	    		bt.leaf(bt.root,bt.count);
	    		
	    		break;  
	   	 	    		    	

	    }
	
   }
   while(select!=0);		
		
	  
		
		
		
	}	
		
}

jemz -1 Master Poster · Answer 2 · 2011-02-10T06:46:39+00:00

When posting error messages, post the entire exception stack trace by highlighting the line on which the error has occurred rather than just posting the exception message.
Also, why does left() method take a count? Is this method for counting leaf nodes? Returning all the values of leaf nodes?
You check for node.llink != null && node.rlink != null , but what happens if one of them is null and the other isn't? You still end up calling leaf() method which doesn't have a NULL check and hence the exception.

hello sir thank you for the reply and i would like to ask apologize by not highlighting the line...I change my method leaf().Is this the correct way of getting the values of all the leaf in a tree?please correct me if i am wrong.Thank you in advance hoping for your positive response...Again I am sorry sir.

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

        
      public void leaf(Node nd)
      {
      	 if(nd!=null)  
      	 {
      	   	
      	  if(nd.llink == null && nd.rlink == null)
      	  {
      	    System.out.print(nd.num +" ");	
      	  }	
      	    
      	 else
      	 {
      	   leaf(nd.llink);
      	   leaf(nd.rlink);
      	 }
       }	
     }  
       
      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!");
		count++;
	    return;

      }
  
      
     
      temp=root;
      count++;
      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;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }
	public static void main(String args[])
	{
		
		Scanner console = new Scanner(System.in);
		BinaryTree bt = new BinaryTree();
                int select=0;
        
   do{
        System.out.print("Select your Choice: ");
         select = console.nextInt();
	    switch(select)
	    {  	     	
	    	case 4:
	    		bt.leaf(bt.root);
	    		break;
	    }
   }
   while(select!=0);			
	}		
}

jemz -1 Master Poster · Answer 3 · 2011-02-11T06:07:25+00:00

What's your end goal here? Printing out the values of the leaf nodes or returning them to the caller?
Also, since you have written almost all the code here, you need to come up with your own ways of verifying the correctness of your code rather than asking others to verify. A few test cases which I can come up with are:
Pass the root (which would be NULL) of an empty binary tree -> should print nothing

Pass a tree containing just a single node (i.e. the root) -> should print root value

Pass a tree created using the values (1, 2, 3, 4) -> output should be 4

Pass a tree created using the values (4, 3, 2, 1) -> output should be 1

Pass a tree created using the values (10, 3, 20, 1, 4, 15, 25) -> output should be (1, 4, 15, 25)

Give it a try!

Hello sir I am printing the values of my leaf nodes. I am just asking if i got the right way of getting the leaf values and if it is efficient i know you also have your own code in this which is more efficient...

Sir about the test above can you give me the example?so that i can have idea and work with it?Thank you in advance hoping for your positive response...

jemz -1 Master Poster · Answer 4 · 2011-02-17T10:37:48+00:00

OK

Likewise, I'm implying that you don't need my help to confirm that your algorithm works. You can run the test cases I posted above (once through code and once by using pen n paper) to confirm the same. Also, assuming that this is for some university course, first concentrate on correctness, then on performance/speed.

Example as in code? No. The entire purpose of giving the least possible information of my posts have to do with you learning how to start thinking the right way. Have you been implementing this code just based on the suggestions/algorithm posted? If not, I'm sure you can at least try rather than directly asking for assistance. How do you create a empty tree? How do you create a tree with a single node? How would you create a tree with 3 given numbers? Like I said previously, try it out, it shouldn't be that difficult.

Hello sir sorry for the late reply...is this what you want sir?please correct me if i am wrong.

private Node root;
     private int count;

     
     public boolean isEmpty()
     {
    	
    	return root==null;

     }
     
    
     
	  public int height(Node node)
	  {
	  		if (node == null)
        		return -1;
   			else
               return Math.max(height(node.llink), height(node.rlink)) + 1;
	  	
	  }
   		

        
      public void leaf(Node nd)
      {
      	 if(nd!=null)  
      	 {
      	   	
      	  if(nd.llink == null && nd.rlink == null)
      	  {
      	  	 System.out.print(nd.num +" ");	
      	  }	
      	    
      	 else
      	 {
      	 		leaf(nd.llink);
      	 	    leaf(nd.rlink);
      	 }
        }
      	
      }  
       
      public void max(Node n)
      {
      	if(isEmpty())
      	{
      		System.out.print("Nothing to display!");
      	}
      	
      	if(n!=null)
      	{
      	  
      	  if(n.rlink!=null)
      	     max(n.rlink);
      	   else
	      System.out.print(n.num + " ");
      	}  	
      }		
      
        
        
          
      public void min(Node n)
      {
      	if(isEmpty())
      	{
      	 System.out.print("Nothing to display!");
      	}
      	if(n!=null)
      	{
      	  if(n.llink!=null)
      	  {
      	   min(n.llink);
      	  }
      	  else
      	  {
      	    System.out.print(n.num + " ");
      	  }
      	  	  
      	 }		
      }
        
       
      public void insertNum(int n)
      {
  
      Node temp=null;
      Node current=null;
   
      Node newNode = new Node();
      newNode.num=n;
 
      
      if(isEmpty())
      {
        
        	
		root=newNode;
		if(root==null)
		{
			System.out.print("The tree is empty");
		}
		else{
		
		System.out.println("Successfully inserted!");
		count++;
	    return;
		}
      }
  
      
     
      temp=root;
      count++;
      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;
			 
			  
			  }	
				
		 }
		
      } 
       
   
      }
	public static void main(String args[])
	{
		
		Scanner console = new Scanner(System.in);
		
		BinaryTree bt = new BinaryTree();
		
        int select=0;
        
   do{
   	   
        System.out.println("====Binary Searh Menu=====");
        System.out.println("1: Insert a number");
        System.out.println("2: Find max");
        System.out.println("3: Find min");
        System.out.println("0: Terminate Program");
        System.out.println("==========================");
        System.out.print("Select your Choice: ");
         select = console.nextInt();
   
      
	    switch(select)
	    {
	    	case 1:
	    		
	    		System.out.print("Insert a number: ");
				bt.insertNum(console.nextInt());
		        
		        break;
		        
		        
		    case 2:
		    	
		    	System.out.print("The largest number: " );
	      	   	 bt.max(bt.root);
	      	   	 System.out.println();
	      	  
	    	    break;	  
	    	    	
	    	    	
	    	case 3:
	    		
	    		System.out.print("The smallest number: " );
	      	   	 bt.min(bt.root);
	      	   	 System.out.println();
	      	         break;			
	   	 	    
	  
	    }
   }
   while(select!=0);		
	
	}			
}

~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster · Answer 5 · 2011-02-22T17:11:05+00:00

I'm afraid no. What I want you to do is to re-read this post again and come up with a small sample snippet/test method which creates hard-coded trees based on the test case, call the leaf() method on them and check whether the output is the same as that mentioned in the test case.

jemz -1 Master Poster · Answer 6 · 2011-02-22T21:54:28+00:00

I'm afraid no. What I want you to do is to re-read this post again and come up with a small sample snippet/test method which creates hard-coded trees based on the test case, call the leaf() method on them and check whether the output is the same as that mentioned in the test case.

Hello sir, Thank you for the patience, you mean that the max method inputting the 1234 which would display 4, and min method inputting 4321 would display 1 is wrong?

but sir why is this wrong? i have the same output with this 2 cases

Pass a tree created using the values (1, 2, 3, 4) -> output should be 4
Pass a tree created using the values (4, 3, 2, 1) -> output should be 1

can you give me an illustration for this example sir please,

Pass the root (which would be NULL) of an empty binary tree -> should print nothing
Pass a tree containing just a single node (i.e. the root) -> should print root value
Pass a tree created using the values (10, 3, 20, 1, 4, 15, 25) -> output should be (1, 4, 15, 25)

Thank you in advance hoping for your positive response...

ztini · Answer 7 · 2011-02-23T11:10:18+00:00

public class Node {

	private Node left;
	private Node right;
	private int value;
	
	public Node(int i) { this.value = i; }
	
	public Node getLeft() { return left; }
	public Node getRight() { return right; }
	
	public void setRight(Node n) { right = n; }
	public void setLeft(Node n) { left = n; }
	
	public int getValue() { return value; }
	public void setValue(int i) { value = i; }
	
	public boolean isLeaf() { return left == null && right == null; }
	
	public static void main(String[] args) {		
	  	Node root = new Node(6);
	  	
		root.setLeft(new Node(4));
		root.setRight(new Node(8));
		 
		root.getLeft().setLeft(new Node(3));
		root.getLeft().setRight(new Node(5));
		  
		root.getRight().setRight(new Node(9));
		root.getRight().setLeft(new Node(7));
		
		System.out.println(root.getValue());
		System.out.println(root.getLeft().getValue());
		System.out.println(root.getRight().getValue());
		
		System.out.println(root.getLeft().getLeft().getValue());
		System.out.println(root.getLeft().getRight().getValue());
		
		System.out.println(root.getRight().getLeft().getValue());
		System.out.println(root.getRight().getRight().getValue());
		
		System.out.println(root.getRight().getLeft().isLeaf());
		System.out.println(root.getRight().getRight().isLeaf());
	}	
}

Console:
6
4
8
3
5
7
9
true
true

That should help you get started at least.

~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster · Answer 8 · 2011-02-23T11:16:10+00:00

I was talking of writing a test method along the lines of:

public void testLeaf() {
  BinaryTree t = new BinaryTree();
  t.leaf();  // prints nothing

  t = new BinaryTree();
  t.add(100);
  t.leaf();  // prints 100

  t = new BinaryTree();
  t.add(1); t.add(2); t.add(3); t.add(4);
  t.leaf();  // prints 4

  t = new BinaryTree();
  t.add(4); t.add(3); t.add(2); t.add(1);
  t.leaf();  // prints 1
}

jemz -1 Master Poster · Answer 9 · 2011-02-27T21:37:36+00:00

I was talking of writing a test method along the lines of:

public void testLeaf() {
  BinaryTree t = new BinaryTree();
  t.leaf();  // prints nothing

  t = new BinaryTree();
  t.add(100);
  t.leaf();  // prints 100

  t = new BinaryTree();
  t.add(1); t.add(2); t.add(3); t.add(4);
  t.leaf();  // prints 4

  t = new BinaryTree();
  t.add(4); t.add(3); t.add(2); t.add(1);
  t.leaf();  // prints 1
}

hello sir thank your the reply okay i will try this sir...i will get back as soon as possible...more power to you sir...

jemz -1 Master Poster · Answer 10 · 2011-03-04T23:51:15+00:00

I was talking of writing a test method along the lines of:

public void testLeaf() {
  BinaryTree t = new BinaryTree();
  t.leaf();  // prints nothing

  t = new BinaryTree();
  t.add(100);
  t.leaf();  // prints 100

  t = new BinaryTree();
  t.add(1); t.add(2); t.add(3); t.add(4);
  t.leaf();  // prints 4

  t = new BinaryTree();
  t.add(4); t.add(3); t.add(2); t.add(1);
  t.leaf();  // prints 1
}

Hi sir i tried it but i am confuse...how can i do like what you did sir...

sir do i need also to make add methode or use my insertnum method?Thank you in advance hoping for your positive response...