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.



Convert binary tree to its Sum tree.


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

Complete Code:


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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

  • traex

    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.

    • Dev Kashyap

      I agree. Its not required at all.

%d bloggers like this: