#700
Search in a Binary Search Tree
Easy BST walk
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the node with a given value in a BST and return its subtree, or null.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: find the node with a value.
Why this works: smaller → go left, bigger → go right. Never search both sides.
Example: find 2 in 4 (2 (1, 3), 7)
2 < 4 → left → found 2✦Hints open one at a time
Smaller values live on the left, larger on the right.
You never need to search both sides.
↗Approach
Walk down from the root, going left or right by comparison, until you find the value or fall off the tree.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode cur = root;
while (cur != null && cur.val != val) {
cur = val < cur.val ? cur.left : cur.right;
}
return cur;
}
}!Common mistake
Searching both subtrees like an ordinary binary tree — that throws away the BST advantage.
Complexity
- Time: O(h).
- Space: O(1) iterative.
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon