Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root:
            if val == root.val:
                return root
            elif val < root.val:
                root = root.left
            else:
                root = root.right
        return None
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root) {
            if (val == root->val) return root;
            else if (val < root->val) root = root->left;
            else root = root->right;
        }
        return nullptr;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (val == root.val) return root;
            else if (val < root.val) root = root.left;
            else root = root.right;
        }
        return null;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    while (root) {
        if (val === root.val) return root;
        else if (val < root.val) root = root.left;
        else root = root.right;
    }
    return null;
};
      

Problem Description

Given the root of a binary search tree (BST) and an integer val, you are to search for a node in the BST whose value equals val. If such a node exists, return the subtree rooted at that node. If the node does not exist, return null (or None).

• Each node in the BST contains a unique integer value.
• You must return the entire subtree rooted at the found node, not just the value.
• If the value does not exist, return null.
• The input is a valid BST, which means for any node, all values in the left subtree are less, and all values in the right subtree are greater.

Thought Process

To solve this problem, we first consider how a binary search tree (BST) works. In a BST, for any node, all nodes in the left subtree have smaller values, and all nodes in the right subtree have larger values. This property allows us to efficiently search for a value, rather than checking every node one by one (which would be required in a regular binary tree).

The naive approach would be to traverse every node (using DFS or BFS) and compare each node's value with val. However, this ignores the BST property and would result in O(n) time complexity, where n is the number of nodes.

Instead, we can use the BST property to prune our search. At each node, we compare val with the current node's value:

• If val is equal, we've found the node and can return it.
• If val is less, we know the node must be in the left subtree.
• If val is greater, the node must be in the right subtree.

Solution Approach

We will use an iterative approach (though recursion works equally well for this problem) to search for val in the BST:

1. Start at the root node.
2. While the current node is not null:
   • If val equals the current node's value, return the current node (this includes its entire subtree).
   • If val is less than the current node's value, move to the left child.
   • If val is greater than the current node's value, move to the right child.
3. If you reach a null node, the value is not in the BST, so return null.

We use an iterative loop to avoid the overhead of recursion, but either approach is valid. This solution efficiently leverages the BST property, which is the key optimization.

Example Walkthrough

Let's say our BST looks like this:

        4
       / \
      2   7
     / \
    1   3
  

Suppose val = 2.

1. Start at root (4). 2 < 4, so move to left child.
2. Now at node (2). 2 == 2, so we've found the node. Return this node (which includes its left and right children: 1 and 3).

If val = 5:

• Start at root (4). 5 > 4, move to right child.
• Now at node (7). 5 < 7, move to left child (which is null).
• Null node reached, so return null (5 is not in the tree).

Time and Space Complexity

• Brute-force approach: Traversing every node (DFS/BFS) is O(n) time and O(n) space in the worst case.
• Optimized BST search: Each step eliminates half the tree (like binary search), so time complexity is O(h), where h is the height of the tree. In the best case (balanced BST), h = log n. In the worst case (skewed tree), h = n.
• Space complexity: For the iterative approach, O(1) extra space is used. For the recursive approach, O(h) stack space is used.

Summary

By taking advantage of the BST property, we can efficiently search for a value without traversing the entire tree. At each step, we decide whether to go left or right based on a simple comparison, similar to binary search. This makes the algorithm much faster than a brute-force approach. The solution is both concise and efficient, making it an elegant way to search in a BST.