Determine whether a tree has one child

• (2 Pages)
• 1
• 2

21 Replies - 1141 Views - Last Post: 17 October 2011 - 08:33 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=251550&amp;s=7717b20986929d0c086ec96daa163333&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#16 imu_1

• D.I.C Regular

Reputation: -6
• 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 ?

#17 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11798
• Posts: 44,322
• Joined: 27-December 08

Re: Determine whether a tree has one child

Posted 17 October 2011 - 03:51 PM

Looks good to me.

#18 imu_1

• D.I.C Regular

Reputation: -6
• 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

#19 imu_1

• D.I.C Regular

Reputation: -6
• 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 ?

#20 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11798
• Posts: 44,322
• 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.

#21 imu_1

• D.I.C Regular

Reputation: -6
• 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

#22 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11798
• Posts: 44,322
• 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.