Convert Binary Tree to Sum Tree


Asked In: yahoogooglebind

Given a Binary Tree , Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.

Example:

For example, the following tree
10
/ \
-2 6
/ \ / \
8 -4 7 5

should be changed to
20(4-2+12+6)
/ \
4(8-4) 12(7+5)
/ \ / \
0 0 0 0

Problem level: Medium