convert binary tree to sum tree in Java

Question

REFERENCE I am copy pasting the problem and the solution that works in C, I am not able to get this working in Java. I understand primarily it is because in Java parameters are passed by value and that is causing problem to maintain state of "old_value". But I even tried changing it to a custom MyInt with set and get, still not able to get this working. So, probably I am missing something else too here. Kindly suggest.

Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.

For example, the following tree

              10
           /      \
         -2        6
       /   \      /  \ 
      8     -4    7    5

should be changed to

             20(4-2+12+6)
           /      \
      4(8-4)      12(7+5)
       /   \      /  \ 
      0      0    0    0

Code:

int toSumTree(struct node *node)
{
    // Base case
    if(node == NULL)
      return 0;


// Store the old value
int old_val = node->data;

// Recursively call for left and right subtrees and store the sum as
// new value of this node
node->data = toSumTree(node->left) + toSumTree(node->right);

// Return the sum of values of nodes in left and right subtrees and
// old_value of this node
return node->data + old_val;

}

Java Code:

public static int sumTree(Node node){
        if(node == null)
            return 0;
        MyInt old_value = new MyInt(node.data);
        node.data = sumTree(node.left) + sumTree(node.right);
        return node.data + old_value.getData();
    }

Since you didn't post your Java code - it's not easy to find your errors... — Nir Alfasi
As long as you use int, the things are copied by value. OTOH Integer is immutable, so it does not matter if you pass it by value or by reference. If you pasted your Java code, we'd have better chances to see what's wrong with it. — 9000
Your C code is only passing things by value anyway (specifically it's passing pointers by value), so I can't see how that aspect of Java would break anything. — user253751
Aah .. I completely missed that. Then the current code should work as it is in Java ? I must be doing something stupid then. — Andy897

Andy897 Andy897 · Accepted Answer · 2015-02-08T18:45:36

I was running wrong tests. Same code logic will work in Java as well as rightly pointed out in comments that pass by value does not make a difference because value is getting returned. The following is the working Java Code:

public static int sumTree(TreeNode node){
        if(node == null)
            return 0;
        int old_value = node.value;
        node.value = sumTree(node.left) + sumTree(node.right);
        return node.value + old_value;
    }

convert binary tree to sum tree in Java

1 Answers