Binary Search Tree (BST) Worst Case
ฝัง
- เผยแพร่เมื่อ 8 ก.พ. 2025
- What is the worst-case time complexity to search an element in a binary search tree (BST) ?
►Binary Search Tree Videos:
Binary Search Tree (BST) Worst Case: • Binary Search Tree (BS...
Binary Search Tree Example: • Binary Search Tree Exa...
Binary Search Tree Algorithm: • Binary Search Tree (BS...
Create A Binary Search Tree: • Create A Binary Search...
Check out my site: www.EverythingComputerScience.com
Please subscribe for more videos and updates !
Resources:
Website:
typeocaml.com/2...
University of Wisconsin:
pages.cs.wisc.e...
pages.cs.wisc.e...
NYU:
cs.nyu.edu/cou...
StackOverFlow:
stackoverflow.c...
thanks man I have a midterm today and this helped a lot
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)
How many worst cases are there for N nodes?
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)?
i think you are referring to depth when you say height. not bad though. clear, short explanation.
So if I wanted to do an inorder traversal of the tree and print the data, the complexity would be O(n)?
yes , definately it will.
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 :)
Your explanation of the worst case for BST is correct; however, all of your notations and are incorrect.
Hi,
Could you explain what you mean please, that way if I did make a mistake I can correct it ?
Thanks;
randerson112358
mohammad khizar already pointed out.
ur awesome
Thank you +numifye !