Problem

Given the root node of a binary search tree (BST) and a value, the problem is to find the node in the BST whose value equals the given value, and return the subtree rooted with that node. If such a node doesn't exist, we should return NULL.

Example

Consider the folllowing binary search tree:

1    4
2   / \
3  2   7
4 / \
51   3

If we want to search for the value 2, we would return the following subtree:

1  2
2 / \
31   3

On the other hand, if we want to search for the value 5, we should return NULL, because there's no node in the given BST that has a value of 5.

Solution Approach

This problem can be solved using a simple greedy approach. Since the given tree is a BST, we can use the properties of a BST to reduce the search space at each step.

While traversing the BST, if the current node's value is smaller than the given value, then the desired node must be on the right side of the current node. Conversely, if the current node's value is larger than the given value, then it must be on the left side of the current node. This ensures that we traverse only the necessary parts of the tree to find the target node.

Python Solution

1
2python
3class Solution:
4    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
5        if root == None: # base case: if the current node is None
6            return None
7        if root.val == val: # if the current node's value equals the target value
8            return root
9        elif root.val > val: # if the current node's value is larger than the target value
10            return self.searchBST(root.left, val) # then the desired node must be on the left side
11        else: # if the current node's value is smaller than the target value
12            return self.searchBST(root.right, val) # then it must be on the right side

Java Solution

1
2java
3public class Solution {
4    public TreeNode searchBST(TreeNode root, int val) {
5        if (root == null) // base case: if the current node is null
6            return null;
7        if (root.val == val) // if the current node's value equals the target value
8            return root;
9        else if (root.val > val) // if the current node's value is larger than the target value
10            return searchBST(root.left, val); // then the desired node must be on the left side
11        else // if the current node's value is smaller than the target value
12            return searchBST(root.right, val); // then it must be on the right side
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4  searchBST(root, val) {
5    if (root == null) // base case: if the current node is null
6      return null;
7    if (root.val == val) // if the current node's value equals the target value
8      return root;
9    else if (root.val < val) // if the current node's value is smaller than the target value
10      return this.searchBST(root.right, val); // then it must be on the right side
11    else // if the current node's value is larger than the target value
12      return this.searchBST(root.left, val); // then the desired node must be on the left side
13  }
14}

C++ Solution

1
2cpp
3class Solution {
4public:
5    TreeNode* searchBST(TreeNode* root, int val) {
6        if (root == NULL) // base case: if the current node is null
7            return NULL;
8        if (root->val == val) // if the current node's value equals the target value
9            return root;
10        else if (root->val > val) // if the current node's value is larger than the target value
11            return searchBST(root->left, val); // then the desired node must be on the left side
12        else // if the current node's value is smaller than the target value
13            return searchBST(root->right, val); // then it must be on the right side
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public TreeNode SearchBST(TreeNode root, int val) {
5        if (root == null) // base case: if the current node is null
6            return null;
7        if (root.val == val) // if the current node's value equals the target value
8            return root;
9        else if (root.val > val) // if the current node's value is larger than the target value
10            return SearchBST(root.left, val); // then the desired node must be on the left side
11        else // if the current node's value is smaller than the target value
12            return SearchBST(root.right, val); // then it must be on the right side
13    }
14}

Each solution above recursively searches the BST for the given value, navigating either to the left or right child of the current node in each recursion based on comparisons between the current node's value and the target value.In this problem, the recursive approach proves to be very effective because it leverages the properties of a BST. Each recursion reduces the search space by half, making this an efficient solution that operates with a time complexity of approximately O(log n) in the best and average cases, where n is the number of nodes in the tree.

In the worst case scenario, where the BST is skewed to the left or right (meaning it behaves more like a linked list rather than a tree), the time complexity degenerates to O(n).

Despite this worst-case scenario, this solution is still ideal for this problem as it's simple, elegant, intuitive and doesn't require any additional data structures.

The space complexity for this solution is O(h), where h is the height of the tree. This space is used by the call stack during the recursion.

It should be noted that this solution makes an assumption that the tree is a BST. If the tree is not a BST, the solution could fail because we are making decisions based on the properties of BSTs.

Lastly, the solution is safe and does not modify the given BST. All changes are made on new, separate copies of subtrees rooted by the node with the required value. This ensures the original tree remains unaffected, maintaining data integrity.