LeetCode: 700. Search in a Binary Search Tree

The Problem

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

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

Constraints:

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

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

TreeNode* searchBST(TreeNode* root, int val) {

	if (root == nullptr) return nullptr;
    if (root->val == val) return root;

    TreeNode* left = searchBST(root->left, val);
    if(left != nullptr) return left;

    return searchBST(root->right, val);

}

This code is a recursive function that searches for a specific value in a Binary Search Tree (BST) and returns the node that contains that value. Let's break it down step by step:

1. The function takes two inputs: a pointer to the root of the current subtree (TreeNode* root) and the value you're searching for (int val).
2. The function starts by checking if the root is a null pointer, which means we've reached the end of the current branch and haven't found the value. In that case, the function returns a null pointer, indicating that the value was not found in the current subtree.
3. If the root's value (root->val) is equal to the value we're searching for (val), then we've found the node containing the value. In this case, the function immediately returns the pointer to the current root node.
4. If the value we're searching for is not found at the current root, the function continues searching. It first calls itself recursively on the left subtree (root->left) and stores the result in the left variable. This recursive call searches the left subtree for the value.
5. After the recursive call, the function checks if the left node is not a null pointer. If it's not null, this means the value was found in the left subtree, and the function returns the left node immediately. This is done to ensure that the function returns the correct node that contains the value.
6. If the left node is null (meaning the value was not found in the left subtree), the function then calls itself recursively on the right subtree (root->right) to search for the value in the right subtree.
7. The final return statement is reached only if the value is not found in the current subtree (root is not null), nor in the left subtree (left is null), and also not in the right subtree. In this case, the function will return a null pointer to indicate that the value was not found in the entire BST.