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?

Linear search results in a worst case of `O(n)`. Binary search is `O(log n)` — dursk, Dec 23 '14 at 17:33
Did you read the linked Wikipedia page? http://en.wikipedia.org/wiki/Binary_search_tree — Oliver Charlesworth, Dec 23 '14 at 17:33
@mattm when we begin search from root node, isn't it always going to be a binary search? — ringord, Dec 23 '14 at 17:35
No, it isn't. It depends on the order that the elements were added to the tree. — Barmar, Dec 23 '14 at 17:36
complexity of balanced binary tree: http://stackoverflow.com/a/13093274/550393 — 2cupsOfTech, Feb 22 '16 at 17:37

user123 · Accepted Answer · 2014-12-23T17:39:01.917

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.

@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`. — Barmar, Dec 23 '14 at 17:38

score 2 · Answer 2 · answered Dec 23 '14 at 17:36

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)

answered Dec 23 '14 at 17:36

zeroha

41
3

Big O Complexity in Binary Search Tree(BST)

2 Answers2