285. Search in a Binary Search Tree

Use the BST ordering: at each node go left if val is smaller, right if larger, stop when equal or off the tree.

Follow the ordering

while root and root.val != val:
    root = root.left if val < root.val else root.right
return root

Every comparison discards one subtree, so the search is O(height).

Worked example

BST [4,2,7,1,3], val=2 → go left from 4 to 2 (match) → returns the subtree [2,1,3].

Complexity

• Time: O(h).
• Space: O(1).

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