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

Question

I have been dealing with this problem for some time, and I can not understand the logic. Let's say I have a binary tree that looks something like this:

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 these numbers together to get the total. The code I have 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 decided that it would recursively add one to each level deeper for the left side of the tree (8 → 4 → 2) before crossing the right side, but this doesn’t quite work.

I looked for this method in any number of ways, but it seemed that I could not nail what I was missing. Any help would be greatly appreciated.

Answer 1

You are almost there: you added the results for the left and right subtrees, but you forgot 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 

Answer 2

 public virtual int GetLevelById(int id) { int i = GetParentById(id); if (i == 0) return 1; else return (1 + GetLevelById(i)); }