Convert binary tree to its Sum tree

by

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:

public class TreeToSumTree {
static Node newRoot;
public int SumTree(Node root){
if(root!=null){
int left = SumTree(root.left);//take the left tree sum
int right = SumTree(root.right);//take the right tree sum
int retData = root.data+left+right; // return data left+right+root
root.data = left+right; //update the root with left + right
newRoot = root; //update the new root
return retData; //return
}
return 0;
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(root.data + " " );
display(root.right);
}
}
public static void main(String args[]){
Node root = new Node(5);
root.left = new Node(–1);
root.right = new Node(3);
root.left.left = new Node(–2);
root.left.right = new Node(4);
root.right.left = new Node(–6);
root.right.right = new Node(10 );
TreeToSumTree t = new TreeToSumTree();
System.out.print("Original Tree: ");
t.display(root);
System.out.print("\nSum tree: ");
t.SumTree(root);
//Print the new tree
t.display(newRoot);
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
}
}

view raw
TreeToSumTree.java
hosted with ❤ by GitHub


Output:

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

Related Posts: