Search in a Binary Search Tree

Problem in plain words

You are given the root of a binary search tree and a number val. Find the node whose value equals val and return it — the caller will see that node together with everything below it. If no node has that value, return null.

Example: in the BST with root 6, children 3 and 9, and 3 having children 1 and 4, searching for 3 returns the subtree 3 → 1, 4. Searching for 7 returns null.

Intuition

The BST property says everything in a node's left subtree is smaller and everything in its right subtree is larger. So one comparison at each node tells you which half can possibly contain val, and you can throw the other half away. This is BST search, the tree cousin of binary search.

Approach

1. Start with node = root.
2. While node is not null and node.val != val: move to node.left if val < node.val, otherwise to node.right.
3. Return node — it is either the match or null if you fell off the tree.

Dry run

Java solution

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode node = root;
        while (node != null && node.val != val) {
            node = val < node.val ? node.left : node.right;
        }
        return node;
    }
}

Python solution

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root
        while node and node.val != val:
            node = node.left if val < node.val else node.right
        return node

Complexity

Edge cases and common mistakes

• Searching both subtrees — that works but wastes the BST property and costs O(n). Pick one side per step.
• Returning `true`/the value — the problem wants the node itself so the caller can see its subtree.
• Empty tree — the loop never runs and null is returned, which is correct.