Convert a given tree to sum tree

By | November 30, 2014
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

This is a solution to here: link

  1. public class BuildSumTree {
  2.     public static void main(String[] args) {
  3.         Tree tree = getSumTree();
  4.         tree = convertToSumTree(tree);
  5.     }
  6.     /*
  7.      * http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
  8.      */
  9.     public static int convertToSumTree(Tree tree){
  10.         if(tree==null){
  11.             return 0;
  12.         }
  13.         int lvalue = (tree.left==null)?0:tree.left.value;
  14.         int rvalue = (tree.right==null)?0:tree.right.value;
  15.         tree.value = convertToSumTree(tree.left) + convertToSumTree(tree.right) + lvalue + rvalue;
  16.         return tree.value;
  17.     }
  18.     /*
  19.      * This tree will be converted to a sum tree.
  20.      */
  21.     public static Tree getSumTree(){
  22.         Tree t1 = new Tree(1);
  23.         Tree t2 = new Tree(2);
  24.         Tree t3 = new Tree(3);
  25.         Tree t4 = new Tree(4);
  26.         Tree t5 = new Tree(5);
  27.         Tree t6 = new Tree(6);
  28.         t1.left = t2;
  29.         t1.right = t3;
  30.         t2.left = t4;
  31.         t2.right = t5;
  32.         t3.left = t6;
  33.         return t1;
  34.     }
  35. }