LeetCode #700 Easy

Search in a BST

Return the subtree rooted at the node whose value equals val, or null.

bstbinary-searchtree

02

Intuition

The BST property is a built-in compass: smaller values live left, larger right. Compare at each node and walk one side — it's binary search wearing a tree costume.

How to spot this pattern

A BST turns searching into deciding: at every node one comparison eliminates an entire subtree. Whenever the structure tells you which way to go rather than forcing you to try both, the traversal is a walk, not a search — so it's O(h) and needs no stack, no queue, no recursion.

03

Approach

1

Three-way compare

val == node → done. val < node → go left. val > node → go right.

2

Iterate, don't recurse

A while loop avoids stack frames — the path is a straight walk.

3

Cost is the height

Balanced BST → O(log n); degenerate chain → O(n).

04

Solution & live demo

▶1class Solution:
▶2    def searchBST(self, root, val):
▶3        while root and root.val != val:
▶4            root = root.left if val < root.val else root.right
▶5        return root

05

Common pitfalls

Searching both subtrees like a plain binary tree

✗ Wrong

if not root or root.val == val: return root
return self.searchBST(root.left, val) or self.searchBST(root.right, val)

✓ Right

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

This returns the right node but visits every node, making it O(n) and throwing away the only thing a BST gives you. The ordering means a smaller target cannot possibly be on the right, so half the tree is ruled out at each step without looking at it.

Returning `None` instead of the subtree on a miss

✗ Wrong

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

✓ Right

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

Both are correct here, but the problem asks for the subtree rooted at the match, and the loop-condition form returns exactly that in one exit — the loop stops either on the match or on None, which is already the required answer.

06

Edge cases

Value absent

Walk falls off a null child → return None.

Value at the root

Loop exits immediately.

07

Complexity

Time

O(h)

Space

O(1)

One root-to-node walk.