int calculateDifference(BinaryTree root) {
if (root == null) {
return 0;
}
int result = root.getData() - calculateDifference(root.getLeft())
- calculateDifference(root.getRight());
return result;
};
The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.
sum[l1] - (sum[l2] - (sum[l3] - (sum[l4] - ... = sum[l1] - sum[l2] + sum[l3] - sum[l4]...
![]() |
| Deifference between sum of nodes on even height and sum of nodes on odd height |
