Why is the time complexity of the sum of the values of nodes in a balanced BST O(n)?

Question

I'm trying to learn about Big O notation and I came across a problem. As in this code we're trying to find the sum of the values of the nodes. And as there are 2 calls to sum function so each call will have twice as many calls than before. So why the runtime is O(n) and not O(2^n).

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

Answer 1

If I’m understanding what you’re saying correctly, your argument is essentially that

1. the recursion branches twice at each call,
2. so the number of recursive calls at each level is twice that of the previous level,
3. so the runtime is Θ(2ⁿ).

@amit’s answer points out that in going from step (2) to step (3) there’s a small but key error, namely switching from n (the number of nodes) to h (the height of the tree).

There’s actually another small issue in the line of reasoning, and that’s in going from step (1) to step (2). Imagine, for example, that the tree you’re working with is a degenerate tree where each node has only a left child and no right child. If you trace the recursion here, you’ll find that the number of calls per level doesn’t grow exponentially because half of the calls walk off the tree and terminate immediately. You’re correct that there are at most 2^k recursive calls made per level, but that will overcount the amount of work done.

To get the O(n) bound more directly, instead of counting how many times the recursion branches and relating that to the height, instead think about how many total recursive calls are made. There’s one at the root node, and from there each node spawns two new recursive calls. That makes the total number of recursive calls at most 2n + 1, and since each call does O(1) work the total work done is O(n). This argument works regardless of the tree shape, and it’s a nice one to use in other recursive contexts.