PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q5(a)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

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.

All past exam questions for Data Structure and Algorithms