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
All Answers
total answers (1)
Sum tree
A binary tree is said to be converted in sum tree:
Let’s consider,
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
Output
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