Search in BST LeetCode 700 Guide

LeetCode 700 — Search in a Binary Search Tree gives you the root of a BST and an integer val. Your task is to find the node in the BST whose value equals val and return its subtree (the node itself, with all descendants). If no such node exists, return null.

The return value is the entire subtree rooted at the found node, not just the integer value. This distinction matters: a node in a BST carries left and right children, so returning the node gives the caller access to all its descendants. Returning null signals that val is not present anywhere in the tree.

This problem is a direct application of the defining property of a BST: all nodes in the left subtree are strictly smaller than the current node, and all nodes in the right subtree are strictly larger. That ordering is what makes O(h) search possible.

A Binary Search Tree guarantees that for any node n: every value in n's left subtree is strictly less than n.val, and every value in n's right subtree is strictly greater than n.val. This invariant holds at every node in the tree, not just the root.

This ordering means that at each step we can eliminate half of the remaining tree. If val < node.val, the target cannot exist in the right subtree — we only need to search left. If val > node.val, the target cannot exist in the left subtree — we only need to search right. At each node we make exactly one comparison and discard an entire branch.

The height h of the BST determines performance. A balanced BST has h = O(log n), giving O(log n) search — as fast as binary search on a sorted array. A skewed BST (e.g., all insertions in sorted order) degrades to h = O(n), giving O(n) worst-case. For this problem, the time complexity is stated as O(h).

The recursive solution mirrors the BST property directly. The base case handles two situations: if the current node is null, val is not in the tree — return null. If node.val == val, we found the target — return the node (its entire subtree).

The recursive case applies the BST ordering: if val < node.val, recurse into the left subtree; otherwise (val > node.val), recurse into the right subtree. Each recursive call reduces the search space by one level and eliminates one branch entirely.

Time complexity is O(h) for the recursion depth, where h is the BST height. Space complexity is also O(h) for the call stack — each recursive call adds one frame. For deeply skewed trees, this O(h) stack space can be O(n) in the worst case, which is why the iterative approach is often preferred.

The iterative solution replaces the call stack with an explicit while loop. Start with the current node = root. At each iteration: if node is null, return null; if node.val == val, return node; if val < node.val, move left (node = node.left); else move right (node = node.right).

This loop terminates when either the target is found or node becomes null after falling off the bottom of the tree. Every iteration follows one edge and narrows the search by one level, giving O(h) time — identical to the recursive version.

The key advantage of the iterative approach is O(1) space: there is no call stack. The only variable needed is the current node pointer, which is updated in-place. For very deep or skewed trees, this matters: the recursive version risks stack overflow while the iterative version runs without any additional memory.

Consider the BST [4, 2, 7, 1, 3] — root is 4, left child is 2 (with children 1 and 3), right child is 7. Searching for val = 2: compare 2 with root 4; 2 < 4 so go left to node 2; compare 2 with node 2; 2 == 2 so return node 2 and its entire subtree [2, 1, 3].

Now search the same BST for val = 5: compare 5 with root 4; 5 > 4 so go right to node 7; compare 5 with node 7; 5 < 7 so go left — but node 7's left child is null; node is now null so return null. The value 5 does not exist in the BST.

Both searches required only 2 comparisons on a tree with 5 nodes. This demonstrates the O(h) = O(log n) efficiency on a balanced BST — we discard roughly half the remaining nodes at each step without ever visiting them.

Python recursive: def searchBST(root, val): if not root or root.val == val: return root; return searchBST(root.left, val) if val < root.val else searchBST(root.right, val). Python iterative: while root and root.val != val: root = root.left if val < root.val else root.right; return root. The iterative version is 2 lines after initialization.

Java recursive: if (root == null || root.val == val) return root; return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val). Java iterative: while (root != null && root.val != val) { root = val < root.val ? root.left : root.right; } return root. Both O(h) time; iterative is O(1) space.

Both recursive and iterative implementations are remarkably concise — the iterative version is 4 lines in any language. The key insight is that the ternary expression (go left or right) compresses the entire BST ordering rule into a single conditional, making the code mirror the algorithm description one-to-one.

Search in BST is the foundation of the BST problem family. Related problems that build directly on this pattern include Validate Binary Search Tree (LeetCode 98), which checks the BST invariant holds at every node using range-based validation; Lowest Common Ancestor of a BST (LeetCode 235), which uses BST ordering to navigate toward the two target nodes simultaneously; and Insert into a BST (LeetCode 701), which uses the same search path to find the correct insertion point.

Kth Smallest Element in a BST (LeetCode 230) uses inorder traversal of the BST (which yields values in sorted order) to find the kth element. Delete Node in a BST (LeetCode 450) combines search with restructuring — find the target node, then handle three cases: no children, one child, or two children. Both problems extend the search logic of LeetCode 700.

Mastering BST search gives you the building block for all BST problems. The pattern is always: compare target with current node, navigate left or right based on BST ordering, repeat until found or null. This same directional navigation appears in insert, delete, validate, and LCA problems across the BST family.