Search in a BST
Return the subtree rooted at the node whose value equals val, or null.
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.
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
python
▶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
Edge cases
Value absent
Walk falls off a null child → return None.
Value at the root
Loop exits immediately.
06
Complexity
Time
O(h)
Space
O(1)
One root-to-node walk.