LeetCode · #700

Search in a Binary Search Tree Solution

Exploit the BST ordering property so each comparison removes an entire subtree from consideration.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #700

🏗️

Pattern

BST search — one-path elimination

Given the root of a BST and an integer val, return the subtree rooted at the node with that value. If it does not exist, return null.

Example

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

Section Two · Approach 1

DFS on Both Sides — O(n)

Treat the BST like a general binary tree and recursively search both left and right subtrees.

Problem: This ignores the BST property. If the target is smaller than the current node, the entire right subtree is guaranteed to be useless.

Section Three · Approach 2

BST-Guided Search — O(h)

At every node, compare val with node.val:

If equal, return this node.
If smaller, continue only in the left subtree.
If larger, continue only in the right subtree.

💡 Mental model: It is binary search on a linked structure. Each comparison tells you which half of the remaining values can be thrown away immediately.

Iterative is ideal here: The logic is just a while-loop over one root-to-leaf path, so recursion adds no real benefit.

Section Four · Trace

Visual Walkthrough

Search for 2 in [4,2,7,1,3]

Section Five · Implementation

Code — Java & Python

Java — iterative

 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;
    }
}

Python — iterative

 class Solution:
def searchBST(self, root, val: int):
while root and root.val != val:
            root = root.left if val < root.val else root.right
return root

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
General DFS	O(n)	O(h)
BST-guided search	O(h)	O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Why it matters
Target is root	Return immediately after first comparison.
Target missing	Eventually hit null and return null.
Skewed BST	Height becomes O(n), so search also becomes O(n).

⚠ Common Mistake: Recursing into both subtrees as if this were a general binary tree. BST ordering is the whole reason the search is fast.

← Back to BST problems

LearningTree

LC 700 · Search in a Binary Search Tree — Solution & Explanation | DSA Guide