Transform to Sum Tree
Given a Binary Tree where each node has positive and negative values. 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.
For example, the following tree 10 / \ -2 8 / \ / \ 6 -5 -7 5 Should be converted to: 5(1-2-2+8) / \ 1(6-5) -2(-7+5) / \ / \ 0 0 0 0
A binary tree is said to be converted in sum tree:
For any intermediate node having two child at kth level
Value of the node must be updated as
Sum of right subtree of the node+ sum of left subtree of the node
Now consider both the right & left child has been already converted to their update node values having respective subtree sums up to (k+1)th level (from bottom to (k+1)th level).
So the node value should be updated as: right child value + left child value + subtree sums up to (k+1)th level
=old right child value + old left child value + new left child value (sum of subtrees up to (k+1)th level) + new right child value (sum of subtrees up to (k+1)th level).
So, here we can develop our recursive function to develop the algo
C++ implementation for Transform to Sum Tree
Explanation with example:
Let’s see how the function solves the above example.need an explanation for this answer? contact us directly to get an explanation for this answer