3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

The book is correct, because $b\leq 2n$, so you visit no more than $3n$ nodes, which is $O(n)$, and $b\leq 2n$ because no node has more than two leaves. You correctly say that $b$ grows proportional to $n$, which is exactly the key.

Just for clarity, Big-Oh notation means "grows proportional to, ignoring constant factors" (roughly), which is why we say that $3n\in O(n)$, even though one is a multiple of the other, and $6n^2+3n+42\in O(n^2)$ and $42e^n\in O(e^n)$, for example.

(actually, $O(n)$ means, "is not more than $cn$". For "is proportional to $n$", use $\Theta(n)$ instead of $O(n)$).

$\endgroup$
  • $\begingroup$ @CowPowPow What David said is still true. The question only exists because the meaning of $\mathcal{O}(n)$ is misunderstood. In either case, the page he links to contains lots of useful info, and you would do well to read it and traverse its links, using the algorithm you have in your question ;) $\endgroup$ – Lieuwe Vinkhuijzen Dec 30 '16 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.