LeetCode //C - 700. Search in a Binary Search Tree

700. Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
?

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

• The number of nodes in the tree is in the range [1, 5000].
• $1<=Node.val<=10^7$
• root is a binary search tree.
• $1<=val<=10^7$

From: LeetCode
Link: 700. Search in a Binary Search Tree

---

Solution:

Ideas：

This function recursively searches the BST: if the val is less than the current node’s value, it searches the left subtree; if val is greater, it searches the right subtree. When the value is found, it returns the current node, which is the root of the subtree containing all nodes with values that make the subtree a valid BST. If the search ends at a NULL node (i.e., the value is not found), it returns NULL.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    // Base case: root is null or root's value is the one we're searching for
    if (root == NULL || root->val == val) {
        return root;
    }
    
    // Since it's a BST, if the value is less than the root's value,
    // we will search in the left subtree
    if (val < root->val) {
        return searchBST(root->left, val);
    }
    
    // If the value is greater than the root's value,
    // we will search in the right subtree
    return searchBST(root->right, val);
}