They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
Doesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?