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:
Approach:
- Recursively calculate the left sum from left sum tree.
- Recursively calculate the right sum from right tree.
- prepare the return root.data + left sum + right sum.
- Update the root data as root.data = left sum + right sum.
- update the newRoot = root.
- See the code for better understanding.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } |
Output:
Original Tree: -2 -1 4 5 -6 3 10 Sum tree: 0 2 0 8 0 4 0
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.
I agree. Its not required at all.