The book "Cracking the Coding Interview , 6th ed." describes the following method to sum the values of all nodes in a balanced binary search tree, and also claims that this method runs in O(n) time.
int sum(Node node) {
if (node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
It seems to me that this method iterates through every node in the tree exactly once, plus one null reference for each leaf in the tree. I would say that n is the number of nodes in the tree, and we visit O(n+b) nodes (where b is the number of leaf nodes, is the number of null nodes traversed) and do constant work there.
How can n be an upper bound if we visit (or attempt to visit) more than n nodes? You might argue that b is constant and so we drop it, but b grows proportionally to n.
Please don't mark this as a duplicate just to get your internet points. Specific questions have specific answers.