Binary Search Tree (BST) Worst Case

What is the worst-case time complexity to search an element in a binary search tree (BST) ?

►Binary Search Tree Videos:

Please subscribe for more videos and updates !

Resources:
Website:

University of Wisconsin:

NYU:

StackOverFlow:

[mayankrawat]

Height of the 2nd tree is not 4 its 3.
Now, how will it be proved that worst case time complexity is O(no. Of nodes)?

[aryans]

How many worst cases are there for N nodes?

[TheAmeer]

O(n) because a binary search tree, also called an ordered search tree, can in the worst case be represented by bad data input (1, 2, 3) for example. If I wanted to find 3, I would need to traverse N elements. If I had balanced data (2, 1, 3) then to find 3, I would need to traverse only the height of the tree, which is O(log n)

[ianwashburn]

i think you are referring to depth when you say height. not bad though. clear, short explanation.

[newtocamelot]

So if I wanted to do an inorder traversal of the tree and print the data, the complexity would be O(n)?

[waqaskhizar]

For the first tree you drew, the height should have been 2 and for the second one it should have been 3 because you don't count the root node. Your welcome :)

[confused]

Your explanation of the worst case for BST is correct; however, all of your notations and are incorrect.

[playdoughfunrs]

thanks man I have a midterm today and this helped a lot