Consider lines of slope -1 passing between nodes (dotted lines in below diagram). Diagonal sum in a binary tree is sum of all node’s data lying between these lines. Given a Binary Tree, print all diagonal sums.
For the following input tree, output should be 9, 19, 42.
1
2 3
9 6 4 5
10 11 12 7
9 is sum of 1, 3 and 5.
19 is sum of 2, 6, 4 and 7.
42 is sum of 9, 10, 11 and 12.