Cracking the Coding Interview - Example 9 (Runtime Example)

Question

This question is related to the depth of binary search tree, but my question is regarding of understanding the example code that is shown below:

int sum(Node node) {
    if (node == null){
        return 0;
    }
    return sum (node.left) + node.value + sum(node.right);
}

The author said the depth of this is roughly log N, I am not sure how to get log N.

Also, my understanding of this code, it seems to be a infinite one. I know it is not, but I can not convince myself. For example, if this is 1~3 array, the node start @ 2, so:

LVL 1:sum(1)+2+sum(3)

LVL 2:sum(sum(0)+1+sum(2))+2+sum(sum(2)+3+sum(0))

LVL 3: ... (The sum(2) will repeat the LVL 1, and it will never end)

Anyone can help me point out the issue?

Thank you!

Answer 1

Decided to turn my comment into an answer:

Binary trees are log n as you keep cutting it in half each time, but this is for a balanced tree. A very unbalanced one would be O(N) if everything was on the right, for example.

So, why is it not infinite?

Since this is recursive it needs a way to stop calling itself, and that is when node is null, then it bails out.

So, in every tree you will eventually reach child nodes that aren't set, and these will stop the recursion, which prevents it from being infinite.

If you remove that if statement then you will get an exception, but in a recursive algorithm that is actually doing something that won't end you would get a stack overflow.