You don't need to compute the sum every time: this is terrible for performance, as you are re-evaluating the same nodes again and again (think of a leaf, it gets evaluated for every node in the chain!).
A tree that has the property you described follows the following rule:
for each node:
- if I'm a leaf, I can hold any value
- otherwise, my value must be f(right) + f(left)
where f(node) is defined as:
- If n is a leaf, f(n) = value(n)
- if n is not a leaf, f(n) = 2*value(n)
This is because leaves only carry their own weight, while nodes bring both their value and the value of their subtrees (hence 2x)
There may be some edge cases that I missed, but the gist of the solution would become something like:
boolean isValidNode(node) {
if (!isLeaf(node)) return node.value == f(node.left) + f(node.right);
else return true;
}
int f(node) {
if (node==null) return 0;
else if (isLeaf(node)) return node.value;
else return 2*node.value;
}
boolean isValidNodeRec(node) {
if (node==null) return true;
else return isValidNode(node) && isValidNodeRec(node.left) && isValidNodeRec(node.right);
}
boolean isValidTree(root) {
isValidNodeRec(root);
}