Question

Write down the Recurrence Relation for binary search tree; solve it using iterative method and give answer at the end in asymptotic form.

Answer 1

Binary search tree is nothing but a binary tree which are based on nodes.The right subtree contains various nodes but they are greater than that of the node's key.The left sub tree of the node is basically less o shall be equal to the parent node.

The recurrence relation is =T(n)=T(n/2)+1