Check if a tree is a sum tree

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

This is the solution to here: link

  1. public class BuildSumTree {
  2.     public static void main(String[] args) {
  3.         Tree tree = Tree.getSumTree3();
  4.         System.out.println(ifSumTree(tree, new MyInteger(0)));
  5.     }
  6.     /*
  7.      * http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
  8.      */
  9.     public static boolean ifSumTree(Tree tree, MyInteger sum){
  10.         if(tree==null||(tree.left==null&&tree.right==null)){    //return true if tree is null or leaf
  11.             sum.i = 0;
  12.             return true;
  13.         }
  14.         int lvalue = (tree.left==null)?0:tree.left.value;
  15.         int rvalue = (tree.right==null)?0:tree.right.value;
  16.         MyInteger lsum = new MyInteger(0);
  17.         MyInteger rsum = new MyInteger(0);
  18.         if(ifSumTree(tree.left, lsum)&&ifSumTree(tree.right, rsum)){
  19.             sum.i = lsum.i + rsum.i + lvalue+rvalue;
  20.             boolean result = sum.i==tree.value;
  21.             return result;
  22.         }
  23.         return false;
  24.     }
  25.     /*
  26.      * This is a sum tree. This tree will be checked if it is a sum tree
  27.      */
  28.     public static Tree getSumTree3(){
  29.         Tree t1 = new Tree(34);
  30.         Tree t2 = new Tree(12);
  31.         Tree t3 = new Tree(5);
  32.         Tree t4 = new Tree(3);
  33.         Tree t5 = new Tree(3);
  34.         Tree t6 = new Tree(2);
  35.         Tree t7 = new Tree(3);
  36.         Tree t8 = new Tree(1);
  37.         Tree t9 = new Tree(2);
  38.         Tree t10 = new Tree(1);
  39.         Tree t11 = new Tree(1);
  40.         Tree t12 = new Tree(1);
  41.         t1.left = t2;
  42.         t1.right = t3;
  43.         t2.left = t4;
  44.         t2.right = t5;
  45.         t4.left = t8;
  46.         t4.right = t9;
  47.         t5.left = t10;
  48.         t5.right = t11;
  49.         t11.right = t12;
  50.         t3.left = t6;
  51.         t3.right = t7;
  52.         return t1;
  53.     }
  54. }