Convert binary tree to its Sum tree

Objective: Given a binary tree, write an algorithm to convert it into its Sum tree.

What is Sum tree: Sum tree of a binary tree, is a tree where each node in the converted tree will contains the sum of the left and right sub trees in the original tree.

Example:

 

Convert binary tree to its Sum tree.

Approach:

  1. Recursively calculate the left sum from left sum tree.
  2. Recursively calculate the right sum from right tree.
  3. prepare the return root.data + left sum + right sum.
  4. Update the root data as root.data = left sum + right sum.
  5. update the newRoot = root.
  6. See the code for better understanding.

Complete Code:


Output:

Original Tree: -2  -1  4  5  -6  3  10
Sum tree: 0  2  0  8  0  4  0

2 Responses

  1. traex says:

    why do u need to set the newRoot in line13? you are not changing any node pointers in the SumTree method. looks like an unnecessary line of code that really does nothing.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: