jollypop - 2 years ago 73
Java Question

# How do I calculate the number of "only child"-nodes in a binary tree?

NOTICE: this is homework-related, but I'm not tagging it as such because the 'homework' tag is marked as obselete (?)

Using the following class that implements a binary tree...

``````class TreeNode
{
private Object value;
private TreeNode left, right;

public TreeNode(Object initValue)
{
value = initValue;
left = null;
right = null;
}

public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
{
value = initValue;
left = initLeft;
right = initRight;
}

public Object getValue()
{
return value;
}

public TreeNode getLeft()
{
return left;
}

public TreeNode getRight()
{
return right;
}

public void setValue(Object theNewValue)
{
value = theNewValue;
}

public void setLeft(TreeNode theNewLeft)
{
left = theNewLeft;
}

public void setRight(TreeNode theNewRight)
{
right = theNewRight;
}
``````

}

I need to calculate the number of nodes in the binary tree that are "only children," this being defined as a node that doesn't have another node stemming from its parent.

This is what I have so far:

``````public static int countOnlys(TreeNode t)
{
if(t == null)
return 0;
if(isAnOnlyChild(t))
return 1;
return countOnlys(t.getLeft()) + countOnlys(t.getRight());
}
``````

I don't know how to implement the
`boolean`
method
`isAnOnlyChild(TreeNode t)`

You are pretty close and have the traversal looking good but in your Treenode you do not have a link between a child and its parent. So You can not tell from say a left child if a sibling (right child) exists.

You could have a parent Treenode (along with left and right) so you could check how many children a given node's parent has. Or as ajp15243 suggested, instead use a method that checks how many children a given node has.

Some pseudo code of the latter:

``````//we still need to check if that only child has its own children
if hasOnlyChild(t)
return 1 + checkOnlys(left) + checkOnlys(right)
else
return checkOnlys(left) + checkOnlys(right)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download