Determine whether a tree has one child

  • (2 Pages)
  • +
  • 1
  • 2

21 Replies - 901 Views - Last Post: 17 October 2011 - 08:33 PM Rate Topic: -----

#16 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Determine whether a tree has one child

Posted 17 October 2011 - 03:48 PM

ok, am supposed to write a recursive method to determine whether a node in the tree has one child. Thats the exact question.

Here's what I have done:

 public boolean hasOneLeaf(Node<AnyType> t) 
    { 
	        boolean status;
        	if(t == null) 
			   return false; 
			
			else 
			{
			   	  status = false; 
			   if((t.left != null && t.right == null) || (t.right == null && t.left != null))
        		status =  true;
		    
			 
			 
			    return  status || hasOneLeaf(t.left) || hasOneLeaf(t.right);
			}
}




I tried different combinations and I am getting the right answer. I just posted it here so that you can give me some more inputs on this. If you find any mistake in my logic,pleas let me know. I think it looks good and more simpler now. What do you think ?
Was This Post Helpful? 0
  • +
  • -

#17 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10438
  • View blog
  • Posts: 38,654
  • Joined: 27-December 08

Re: Determine whether a tree has one child

Posted 17 October 2011 - 03:51 PM

Looks good to me.
Was This Post Helpful? 1
  • +
  • -

#18 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Determine whether a tree has one child

Posted 17 October 2011 - 03:58 PM

thanks for the approval macos
Was This Post Helpful? 0
  • +
  • -

#19 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Determine whether a tree has one child

Posted 17 October 2011 - 07:00 PM

It doesnt work. I tried with values 17,82. That should give me true but it doesnt. Can anyone help please ?
Was This Post Helpful? 0
  • +
  • -

#20 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10438
  • View blog
  • Posts: 38,654
  • Joined: 27-December 08

Re: Determine whether a tree has one child

Posted 17 October 2011 - 07:02 PM

Show us all your revised code.
Was This Post Helpful? 0
  • +
  • -

#21 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Determine whether a tree has one child

Posted 17 October 2011 - 07:46 PM

ok,here you go:


import java.util.*;

public class BinaryTree<AnyType extends Comparable<? super AnyType>>
{ 
   public static class Node<AnyType>
   { 
      Node(AnyType theElement) 
	  { 
	    this(theElement, null, null); 
	  } 
	  
	  Node( AnyType theElement, Node<AnyType> lt, Node<AnyType> rt) 
	  { 
	     element = theElement; 
		 left = lt; 
		 right = rt; 
	  } 
	  
	  AnyType element; 
	  Node<AnyType> left; 
	  Node<AnyType> right; 
    } 
	
	private Node<AnyType> root; 
	
	public BinaryTree() 
	{ 
	  root = null; 
	} 
	
	public void insert(AnyType x) 
	{ 
	   root = insert(x,root); 
	} 
	
	public Node<AnyType> insert(AnyType x, Node<AnyType> t) 
	{ 
	
	   
	   if( t == null) 
	   {  
	   // System.out.println("Inside insert");
		return new Node<AnyType>(x,null,null); 
		
	   }
	 int compareResult = x.compareTo(t.element); 
	 
	  if( compareResult < 0) 
	     t.left = insert(x,t.left); 
	
	  else if( compareResult > 0) 
	  t.right = insert(x,t.right); 
	  
	  else 
	    ; 
		
	  return t; 
	}

        public boolean containsOneLeaf() 
	{ 
	    return hasOneLeaf(root);
	}
        
public boolean hasOneLeaf(Node<AnyType> t) 
    { 
	       boolean status;
        	if(t == null) 
			   return false; 
			
			else 
			{
			   	  status = false; 
			   if((t.left != null && t.right == null) || (t.right == null && t.left != null))
        		status =   true;
		     
			  // System.out.println("Status is" + status);
			   System.out.println("t is now" + t.element);
			    return status || hasOneLeaf(t.left) || hasOneLeaf(t.right);
 
			} 
			
			 
	}  


       public static void main (String [] args) 
	{ 
	    BinaryTree<Integer> node =  new BinaryTree<Integer>(); 
		
		node.insert(17); 
	    node.insert(82);
	}
}



Thats the entire code
Was This Post Helpful? 0
  • +
  • -

#22 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10438
  • View blog
  • Posts: 38,654
  • Joined: 27-December 08

Re: Determine whether a tree has one child

Posted 17 October 2011 - 08:33 PM

Actually, I may have guided you wrong earlier for this adaptation. A leaf is when a Node isn't null, but both its left and right pointers are. Use that as a hint to adapt your code.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2