Find the total depth of every node in a binary search tree recursively?

Question

I have been at this problem for awhile now and I can't quite figure the logic. Say I have a binary tree that looks something like the following:

        8                    1 * 0 =  0
      /   \
     4    12                 2 * 1 =  2
    / \   / \
   2   6 10 14               4 * 2 =  8
                                    ----
                                     10

I want to find the depth of each node and add those numbers all together to get a total. The code I've got right now looks something like this:

private int totalDepth(Node node, int depth) 
{
    if(node == null) 
    {
        return 0;
    }

    return totalDepth(node.left, depth + 1) + totalDepth(node.right, depth + 1);
}

I figured this would recursively add one to each level deeper for the left side of the the tree (8 -> 4 -> 2) before traversing the right side, but it doesn't quite work.

I've tweaked this method any number of ways but can't seem to nail down what I'm missing. Any help would be GREATLY appreciated.

Answer 1

You are almost there: you have added up the results for the left and the right subtree, but you have forgotten to add the result for the node itself:

return depth                              // myself
     + totalDepth(node.left, depth + 1)   // my left subtree
     + totalDepth(node.right, depth + 1); // my right subtree