I wrote this in Java (I know that the brackets don't exactly follow the standard way of doing it in Java - so it looks a bit like C#). But I was wondering how this algorithm is percieved. I have seen some iterative ways of solving the problem - but I thought recursion improves readability here.
Every node in a Binary Tree, has to have the value of it's subtree.
8
/ \
3 2
/ \
1 2
Would be an example of such a tree. (1+2 = 3 at the bottom, and 1 + 2 + 3 + 2 = 8 at the top). An empty tree is considered 'valid'.
public boolean isValid()
{
return isValid(root);
}
public boolean isValid(BinaryNode<E> node)
{
if (node == null)
return true;
int sum = sumOfSub(node.getLeft()) + sumOfSub(node.getRight());
if (node.getLeft() != null && node.getRight() != null)
{
if ((Integer) node.getData() != sum)
{
return false;
}
}
else
return true;
return isValid(node.getLeft()) && isValid(node.getRight());
}
private int sumOfSub(BinaryNode node)
{
if (node == null) return 0;
int value = (Integer) node.getData();
return value + sumOfSub(node.getLeft()) + sumOfSub(node.getRight());
}