# 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 <= 10`

^{7}`root`

is a binary search tree.`1 <= val <= 10`

^{7}

**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);
}
```

ðŸ§

Github with all the solution including test cases.

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:

- 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`

). - 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. - 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. - 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. - 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. - 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. - 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.