Past exam question: 2065 Shrawan (Regular / Back), Q5(a)
Open in the Padhaiko appQuestion
Give the recursive searching algorithm for BST (Binary Search Tree).
Solution
Recursive Search Algorithm in BST: Using the BST invariant (), compare key with root->data and recurse into at most one subtree:
Algorithm BST_SEARCH(root, key):
1. If root == NULL or root->data == key:
Return root
2. If key < root->data:
Return BST_SEARCH(root->left, key)
3. Else:
Return BST_SEARCH(root->right, key)
Time complexity: where is tree height ( balanced, worst-case skewed).
Answer:
BST_SEARCH(root, key) returns root if NULL or matched, recurses left if key < root->data, and recurses right otherwise in time.