PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q5(a)

Data Structure and Algorithms · 3 marks

Open in the Padhaiko app

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

Question

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.

All past exam questions for Data Structure and Algorithms