Diagonal Sum of a Binary Tree - GeeksforGeeks

Diagonal Sum of a Binary Tree - GeeksforGeeks

Diagonal Sum of a Binary Tree 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. 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. We strongly recommend to minimize your browser and try this yourself first Algorithm: The idea is to keep track of vertical distance from top diagonal passing through root. We increment the vertical distance we go down to next diagonal. 1. Add root with vertical distance as 0 to the queue. 2. Process the sum of all right child and right of right child and so on. 3. Add left child current node into the queue for later processing. The vertical distance of left child is vertical distance of current node plus 1. 4. Keep doing 2nd, 3rd and 4th step till the queue is empty.

Read full article from Diagonal Sum of a Binary Tree - GeeksforGeeks