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
booleanisAnOnlyChild(TreeNode t)Could someone please help me?
Answer
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)
Source (Stackoverflow)