title: Find the total depth of every node in a binary search tree recursively?
body: <p>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:</p>
  
  <pre><code>        8                    1 * 0 =  0
        /   \
       4    12                 2 * 1 =  2
      / \   / \
     2   6 10 14               4 * 2 =  8
                                      ----
                                       10
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>private int totalDepth(Node node, int depth) 
  {
      if(node == null) 
      {
          return 0;
      }
  
      return totalDepth(node.left, depth + 1) + totalDepth(node.right, depth + 1);
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>