CODEWITHSUNDEEP
javaalgorithmbinary-tree
Andy897
Andy897

Reputation: 7133

convert binary tree to sum tree in Java

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();
    }

Upvotes: 2

Views: 1017

Answers (1)

Andy897
Andy897

Reputation: 7133

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;
    }

Upvotes: 3

Related Questions