Big O Complexity in Binary Search Tree(BST)

Question

i've been reviewing all the stuff i've learned, and found out that this website, and it is saying the worst case of searching in Binary Tree has O(n) complexity. So far i've known, in Binary search tree is a sorted tree that we can search with binary search which has O(log n)-log base 2 probably.

Could anyone explain?

Answer 1

In the absolute worst case, a binary tree with N elements would be like a linked list.
Hence, there would be N levels, and a search would take N traversals.

                                    ~ Root ~
                                      ____
                                     | 42 |
                                     |____|
                                    /      \
                               ____/        \
                              | 13 |         X
                              |____|
                             /      \
                        ____/        \
                       | 11 |         X
                       |____|
                      /      \
                     /        \
                  ...          X

That's why it's O(N) in the worst case.
And this is why we need to balance the trees to achieve O(log N) search.