Calculating node depths of all nodes in a Binary Tree

user_2981518 0
Viewed 675

I'm trying to solve the Node Depths question from Algoexpert. The problem requires you to calculate the sum of depths of all the nodes in a given binary tree. For example, given this tree -

          1
       /     \
      2       3
    /   \   /   \
   4     5 6     7
 /   \
8     9

the sum should be 16.

I wrote a recursive solution to it, which I think is correct, but interestingly enough, only the first test passes, while the remaining test cases fail. Here is my solution-

import java.util.*;

class Program {

  // static variable to hold the final sum
  private static int finalSum = 0;

  public static int nodeDepths(BinaryTree root) {
        // Write your code here.
        int runningSum = 0;
        depthHelper(root.left, runningSum);
        depthHelper(root.right, runningSum);
        return finalSum;
  }
    
    private static void depthHelper(BinaryTree node, int runningSum) {
        if(node == null) return;
        runningSum++;
        finalSum += runningSum;
        depthHelper(node.left, runningSum); 
        depthHelper(node.right, runningSum);
    }

  static class BinaryTree {
    int value;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int value) {
      this.value = value;
      left = null;
      right = null;
    }
  }
}

The algorithm itself is fairly simple.

There is a runningSum variable (initialized to -1 to account for the root) to which I add 1, every time I visit a new node (ie: one level down from it's parent). And, the value of this runningSum variable is added to the finalSum variable at each recursive call.

As an example, at node 2, runningSum is 1, and this gets added to finalSum which was 0. Now finalSum becomes 1. Same for node 3, after which finalSum becomes 2. At node 4, runningSum becomes 2 and finalSum becomes 4.

The first test case passes, and I get this message -

enter image description here

But then, all the subsequent cases fail. I think what may be happening is - the output from the previous test case execution is not cleared, and somehow gets added to the result of the current test case execution.

Here's why I think that may be the reason -

 1. Test case 2 - our code output - 0,  your code output - 16
 2. Test case 3 - our code output - 1,  your code output - 17
 3. Test case 4 - our code output - 2,  your code output - 19
 4. Test case 5 - our code output - 4,  your code output - 23
 5. Test case 6 - our code output - 21,  your code output - 44
 6. Test case 7 - our code output - 42,  your code output - 86

Notice how the result from a previous execution isn't cleared and gets added to the "our code output" of the subsequent execution. For instance, in the second test case, the "your code output" result shows 16 which was actually the result of the first test case.

Is this due to the usage of a global static variable in the code? But I've used the same approach several times on Leetcode, and it worked well there.

Or is there a different bug in my algorithm?

PS - I know using screenshots is frowned upon here, but there is a chance this is a platform-specific issue, so I had to use it.

binary-tree recursion algorithm java
2 Answers

In my opition it is not a bug that this behavior occurs. It is due to making everything static. There are many possibilities to avoid this problem. Two of them explained here:

Using static methods but with stateless class:

public static int nodeDepths(BinaryTree root) {
    // Write your code here.
    return depthHelper(root.left, 1) + depthHelper(root.right, 1);
}

private static int depthHelper(BinaryTree node, int sum) {
    if (node == null) return 0;
    return sum + depthHelper(node.left, sum + 1) + depthHelper(node.right, sum + 1);
}

Create an object (becomes more useful if you are not doing just one operation on the object):

public static int nodeDepths(BinaryTree root) {
    // Write your code here.
    return new Program().depthSum(root); // call to non-static method
    // like this you can use your original implementation, but the
    // class variable (finalSum) has to be non-static too
}

Both implementations are thread-safe.

user_47851100

Looks like their testing platform runs tests with one object of your class. So you should clear finalSum at the end of nodeDepths() method:

public static int nodeDepths(BinaryTree root) {
    // Write your code here.
    int runningSum = 0;
    depthHelper(root.left, runningSum);
    depthHelper(root.right, runningSum);
    int temp=finalSum;  
    finalsum=0; 
    return temp;
}
user_94329670
Related