Search in a Binary Search Tree — LeetCode 700 BST Property in O(h)

Problem Statement#

You are given the root of a Binary Search Tree and an integer val. Return the subtree rooted at the node whose value equals val. If no such node exists, return null.

Constraints:

• Number of nodes is in the range [1, 5000].
• 1 <= Node.val <= 10^7.
• 1 <= val <= 10^7.

Input:  root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Input:  root = [4,2,7,1,3], val = 5
Output: []

Why This Problem Matters#

LeetCode 700 — Search in a Binary Search Tree is the simplest possible BST question. It is a 3-minute warmup at Amazon, Microsoft, Apple, and Meta, but interviewers grade carefully on whether candidates exploit the BST property or treat it as a generic binary tree.

If you walk every node looking for the value, you are O(n) and you fail the signal. If you use the ordering, you are O(h) — O(log n) for balanced and O(n) only for the pathological skewed case.

This is also the gateway to Insert into a BST (LC 701), Delete Node in BST (LC 450), Validate BST (LC 98), Closest BST Value (LC 270), and BST Iterator. Every BST problem starts with the same pruning idea.

The Core Insight#

A BST is a sorted structure. At each node:

• If val == root.val, you found it.
• If val < root.val, recurse left only.
• If val > root.val, recurse right only.

Each step eliminates half the remaining tree, so search time is O(h) — the height of the tree. The iterative version uses O(1) extra space, which is the textbook answer when interviewers ask "can you do better".

Visual Dry Run#

Tree [4, 2, 7, 1, 3], target val = 2:

Result: subtree [2, 1, 3].

For val = 5 we go right to 7, see 5 < 7, go left to null, return null.

Solution (Optimal)#

# Python — recursive O(h) time, O(h) stack
class Solution:
    def searchBST(self, root, val):
        if not root or root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left,  val)
        return self.searchBST(root.right, val)

// JavaScript — iterative O(1) space, the preferred answer
var searchBST = function(root, val) {
    while (root && root.val !== val) {
        root = val < root.val ? root.left : root.right;
    }
    return root;
};

# Python iterative — O(1) extra space
class Solution:
    def searchBST(self, root, val):
        while root and root.val != val:
            root = root.left if val < root.val else root.right
        return root

Time: O(h) — O(log n) for balanced BST, O(n) worst case for skewed. Space: O(h) recursion or O(1) iterative.

Common Mistakes#

• Walking the tree like a generic binary tree (DFS or BFS over every node) — works but signals you do not understand BSTs.
• Returning a boolean instead of the subtree node — read the signature carefully.
• Comparing with <= instead of <, accidentally walking past equal values.
• Recursing both left and right when only one is needed.

Interview Tips#

• Always say "BST property gives me O(h)" before writing code.
• Prefer the iterative version — most interviewers reward the O(1) space variant.
• Discuss balanced vs. skewed: O(log n) vs. O(n) and how AVL/Red-Black guarantees the former.
• Mention this template is reused for Insert, Delete, and Closest Value in BST.

Follow-up Questions#

• Insert into BST (LC 701)? Walk to the null spot using the same comparisons, attach a new node.
• Delete Node in BST (LC 450)? Find the node, then handle 0/1/2-children cases.
• Closest BST Value (LC 270)? Walk and track the closest value seen along the way.
• BST with duplicates? Decide a tie-breaking rule (e.g. equal goes right) and stay consistent.
• Concurrent search? Read-only walk is naturally thread-safe; insert/delete needs locks or persistent BST.

Key Takeaways#

• LeetCode 700 Search in a BST runs in O(h) time and O(1) iterative space.
• The pattern is compare with root.val, walk left or right, repeat.
• Asked at Amazon, Microsoft, Apple, Meta, Bloomberg as a BST warmup.
• Foundation for Insert (LC 701), Delete (LC 450), Closest BST Value (LC 270), Validate BST (LC 98).
• Iterative version is the preferred answer because it uses O(1) extra space.
• Always exploit the BST property; treating it as a generic tree is a red flag.
• For balanced BSTs the runtime is O(log n); only pathological skews degrade to O(n).