Past exam question: 2063 Baishakh (Regular / Back), Q5(a)
Open in the Padhaiko appQuestion
Write an algorithm to search a record in a binary search tree.
Solution
Algorithm BST_SEARCH(root, key):
Algorithm BST_SEARCH(root, key):
1. curr = root
2. While curr != NULL:
If key == curr->key:
Return curr // Record found
Else if key < curr->key:
curr = curr->left
Else:
curr = curr->right
3. Return NULL // Record not found
Runs in time ( balanced, skewed) and space iteratively.
Answer:
BST_SEARCH compares key at each node, moving left when key < curr->key and right when key > curr->key, returning the matching node or NULL in time.