BST Search

Searching a BST

The BST property makes search efficient. At each node, you only need to check one subtree:

        5
       / \
      3   7
     / \ / \
    1  4 6  8

To search for 6: start at 5. 6 > 5, go right to 7. 6 < 7, go left to 6. Found!

To search for 9: 9 > 5, right. 9 > 7, right. 9 > 8, right → NULL. Not found.

Each step eliminates half the tree (on average). This is O(log n) for balanced trees.

Implementation

int bst_search(struct Node *root, int val) {
    if (root == NULL) return 0;
    if (val == root->val) return 1;
    if (val < root->val) return bst_search(root->left, val);
    return bst_search(root->right, val);
}

Returns 1 if found, 0 if not.

Your Task

Implement int bst_search(struct Node *root, int val) that returns 1 if val is in the BST, 0 otherwise.