Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Convert binary tree to its Sum tree

Objec­tive: Given a binary tree, write an algo­rithm to con­vert it into its Sum tree.

What is Sum tree: Sum tree of a binary tree, is a tree where each node in the con­verted tree will con­tains the sum of the left and right sub trees in the orig­i­nal tree.

Exam­ple:

 

Convert binary tree to its Sum tree.

Con­vert binary tree to its Sum tree.

Approach:

  1. Recur­sively cal­cu­late the left sum from left sum tree.
  2. Recur­sively cal­cu­late the right sum from right tree.
  3. pre­pare the return root.data + left sum + right sum.
  4. Update the root data as root.data = left sum + right sum.
  5. update the new­Root = root.
  6. See the code for bet­ter understanding.

Com­plete Code:

Out­put:

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

You may also like...

  • traex

    why do u need to set the new­Root in line13? you are not chang­ing any node point­ers in the SumTree method. looks like an unnec­es­sary line of code that really does nothing.

    • Dev Kashyap

      I agree. Its not required at all.