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 |
can you please help with tracing this recursion
ReplyDeleteHi Manish,
ReplyDeleteHere is the break down of the formula, where for example n1 is the node with value 1, and so on:
root.getData() - calc(root.getLeft()) - calc(root.getRight())=
5 - calc(n2) - calc(n6)=
5 - (2 - calc(n1) - calc(n4)) - (6 - 0 - calc(n8))=
//... we skip a few rows
5 - (2 - (1 - 0 - 0) - (4 - 3)) - (6 - 0 - (8 - 7 - 9)) = -9
If we debug, here is what we see on each step (call of calculateDifference()).
Let's watch data (the current node) and result (the result of the function) on each step.
Note that the result won't be always available because the recursion hasn't got to the end:
1. data 5 result ?
2. data 2 result ?
3. data 1 result ?
4. data null result ?
5. data null result ?
6. data 1 result 1-0-0 (continuation of step 3)
7. data 2 result ?
8. data 4 result ?
9. data 3 result ?
10. data null result ?
11. data null result ?
12. data 3 result 3-0-0 (continuation of step 9)
13. data 4 result ? (continuation of step 8)
14. data null result ?
15. data 4 result 4-3=1 (continuation of step 8)
16. data 2 result 2-1-1=0 (continuation of step 2)
...
Thank you !
ReplyDeleteThis was Helpful ! :)