call stack for recursion logic is not behaving proper in java

Question

I am writing a program to get Sum of depth for a given binaryTree. It's returning proper value with instance value but returning wrong value(greater than expected) if I am printing the returned value from the method. Code with output is as below.
Note: I am having the right solution also but I am posting this solution to understand what wrong happing with the call stack of the recursion. My expectation was in the last stack memory the final value will persist that will be returned to the caller method it returning a different value.

public class NodeDepth_2 {

    static int sum = 0;
    
    public static int nodeDepths(BinaryTree root) {
        Integer depthSum = 0;
        Integer depth = -1;
        int finalValue = nodeDepths(root, depth, depthSum);
        System.out.println("Printing returned value from method: " + finalValue);
        System.out.println("sum from instance variable : " + sum);
        return depthSum.intValue();

    }

    public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
        depth = depth + 1;
        depthSum = depthSum + depth;
        sum = sum + depth;


        if (root.left == null && root.right == null) {
            return depthSum;
        }

        return nodeDepths(root.left, depth, depthSum) + nodeDepths(root.right, depth, depthSum);

    }

    static class BinaryTree {

        int value;

        BinaryTree left;

        BinaryTree right;

        public BinaryTree(int value) {

            this.value = value;

            left = null;

            right = null;

        }

    }

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(1);

        root.left = new BinaryTree(2);

        root.left.left = new BinaryTree(4);
        root.left.left.left = new BinaryTree(8);

        root.left.left.right = new BinaryTree(9);

        root.left.right = new BinaryTree(5);

        root.right = new BinaryTree(3);

        root.right.left = new BinaryTree(6);

        root.right.right = new BinaryTree(7);

        nodeDepths(root);
    }

}

Output is:

Printing returned value from method: 21 // wrong value returned with method return
sum from instance variable : 16 // this is expected value

user_5133585 · Answer

The base case should return depth rather than the accumulated depthSum.

The base case is asking:

What is the depth sum of a subtree that has no child nodes?

It is the depth of that subtree! depthSum would include all the depths of the nodes that we have counted, some of which are not in the subtree that we are asking about, so is incorrect.

Also, the recursive case should also add depth to the sum of both subtrees.

The recursive case is asking:

What is the depth sum of a subtree with two sub-subtrees?

It is the sum of the depth sum of those sub-subtrees, plus the depth of the subtree itself!

Also note that you forgot the case when exactly one of root.left and root.right is null.

After handling those cases, the code would look like:

public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
    depth = depth + 1;
    depthSum = depthSum + depth;
    sum = sum + depth;

    int retVal = depth;

    if (root.left != null) {
        retVal += nodeDepths(root.left, depth, depthSum);
    }

    if (root.right != null) {
        retVal += nodeDepths(root.right, depth, depthSum);
    }

    return retVal;

}

call stack for recursion logic is not behaving proper in java

1 Answers