CODEWITHSUNDEEP
data-structuresbig-obinary-search-tree
ringord
ringord

Reputation: 958

Big O Complexity in Binary Search Tree(BST)

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?

Upvotes: 2

Views: 22887

Answers (2)

user123
user123

Reputation: 9071

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.

Upvotes: 11

zeroha
zeroha

Reputation: 41

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)

Upvotes: 2

Related Questions