Search in a Binary Search Tree
EasyCompare and descend
Problem
Given the root of a BST and a value, return the subtree rooted at the node with that value, or null if absent.
Compare with the node: go left if smaller, right if bigger — halving the tree each step.
The idea
At each node, go left when the key is smaller and right when it is larger. Every comparison eliminates one entire subtree, which is why the walk is O(height) rather than O(n).
The trick
- Iterative and recursive are equally simple; iterative uses O(1) space.
- Reaching null means the key is absent.
Step 1 of 5. Insert 6. Walk down the ordering until we reach an empty spot.
1/5
Optimal
timeO(h)spaceO(1)
Find the empty slot.
1function insert(root, key) {2 if (!root) return new Node(key);3 let cur = root;4 while (true) {5 if (key < cur.val) {6 if (!cur.left) { cur.left = new Node(key); break; }7 cur = cur.left;8 } else {9 if (!cur.right) { cur.right = new Node(key); break; }10 cur = cur.right;11 }12 }13 return root;14}Input
- nodes
- 7, 6 edges
Output
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [4,2,7,1,3], target = 2
- Output:
- true
- Explanation:
- Go left from 4, land on 2.
Example 2
- Input:
- bst = [4,2,7,1,3], target = 5
- Output:
- false
- Explanation:
- 5 isn't present → false.
Example 3
- Input:
- bst = [8], target = 8
- Output:
- true
- Explanation:
- Root is the target.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.