A small but important problem: what is the definition of a BST? I googled it and searched it in some command used book. There is a big difference between two definitions.
1.The left sub-tree of a node has a key less than or equal to that of this node.
2.The right sub-tree of a node has a key greater than to that of this node.
Whether "equal" is allowed here? If it is allowed, the worst case is all nodes are "equal". Then at least for this problem, the O(logn) solution is wrong here.