What is the runtime (using big-O notation) of a search operation in a balanced binary search tree with n nodes? With example and explanation
What is the runtime (using big-O notation) of a search operation in a balanced binary search tree with n nodes? With example and explanation
First lets understand what balanced binary search tree mean:
in balanced binary search tree, at every node , the height difference between left sub tree and right subtree is at most 1
this ensures that at every node, while going down the tree, there are equal number of nodes(max differ by 1) on both sides(left and right subtrees)
now, lets check the search operation on balanced binary search tree with n nodes:
first we will compare root node's value with search value
if search value is less than root's value, then we will move to left subtree, and if greater, then we will move to right subtree,
in both cases the size n will be reduced to n/2 (since we are skipping another subtree, which has at most n/2 nodes)
so, like wise at each node, the size will keep reducing to half, until search value is found: n , n/2 , n/(2^2), n/(2^3)....n/(2^k)
this search will stop when n=2^k //where k is max depth
so, running time will be k = logn
Step by step
Solved in 2 steps with 1 images
