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?

Solution 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.

Solution 2

O(log n) is valid only if btree is balanced. In case of your insertions are all on the same side of the tree, to find something you must traverse all the items, then O(n)

Comments

[ringord]

Oh i understand now. Thanks for the image

[Barmar]

@man.theobsolete You'll get this tree if you insert in the order 42, 13, 11. You'll get a balanced tree if you insert 13, 11, 42.