in the question, it is asked to give implementation of o(n), but the tree is a binary search tree, which is normally used in O(logn). in fact, i can give the same implementation of o(n) for every tree whatsoever. did you mean the complexity should be o(logn), or is the "binary *search*" should be omitted?

There is no mistake in the question.

Recall what I said in class.

You can do somthing in $o(n)$ time (this is little oh) only if you can do it without considering the whole input.

$f(n)=O(g(n))$ means that $g$ bounds $f$ asymptotically, up to a constant factor. Formally, there are $c, n_0$ such that $f(n) \leq c \cdot g(n)$ for $n > n_0$.

$f(n)=o(g(n))$ means that $g$ dominates $f$ asymptotically. Formally, for every $c > 0$ there is $n_0$ such that $f(n) < c \cdot g(n)$ for $n > n_0$.

If $f(n)$ is $o(g(n))$ then $g(n)$ cannot be $O(f(n))$. Intuitively, as $n$ grows, $g(n)$ grows much faster than $f(n)$.

That's correct.

Since every algorithm must check all the nodes in the trees, it is not reasonable to solve it in small-o of n time, as you claimed.

However, we asked you to solve it in O(n) time.

Note that the key inside a node cannot help you to decide what is the size of it sub-tree. Also, the tree is not a balanced tree.

But any "ordinary" algorithm can solve this problem in O(n) for any kind of tree. It's just a matter of passing recursively on all of the tree's nodes and summing them up. That so, why is the tree defined as a "binary search" tree? its properties are not necessary for an algorithm of O(n).

You are right.

The word "search" can be omitted from this exercise.