Closest Binary Search Tree Value
Find the value in a binary search tree that is nearest to a real-number target. A test of using the BST ordering to walk one path instead of visiting every node. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given the root of a binary search tree and a number target, which may have a fractional part. Return the value in the tree that is closest to target, meaning the absolute difference |value - target| is as small as possible.
If two values are equally close (for example, the target sits exactly halfway between them), return the smaller one.
In a binary search tree, every value in a node's left subtree is less than the node's value and every value in its right subtree is greater. All values are distinct. The tree is given in level order, with null marking a missing child.
Example 1
- Input
- root = [8, 3, 12, 1, 6, null, 15], target = 10.2
- Output
- 12
12 is 1.8 away and 8 is 2.2 away. Every other value is farther.
Example 2
- Input
- root = [8, 3, 12, 1, 6, null, 15], target = 7
- Output
- 6
6 and 8 are both 1 away, so the smaller one wins.
Example 3
- Input
- root = [40], target = -1000
- Output
- 40
With a single node, its value is always the answer.
Constraints
- The number of nodes is in the range [1, 10⁴].
- -10⁹ ≤ Node.val ≤ 10⁹, and all values are distinct.
- -10⁹ ≤ target ≤ 10⁹
- The tree is a valid binary search tree.
Practice
Runs 16 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Closest Binary Search Tree Value in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Closest Binary Search Tree Value
Pattern: Walk one BST search path
If this were any binary tree, you would have to look at every node. The BST ordering means you don't. Start at the root and move toward the target the way a normal search would: left if the target is smaller than the node, right if it is larger.
The closest value is always on that search path. Any node you skip is on the far side of a node you visited, so that visited node is already at least as close. Keep the best value seen along the way, and break ties toward the smaller value.
Approach 1: Visit every node
Traverse the whole tree (any order) and keep the value with the smallest distance, preferring the smaller value on a tie. Correct for any binary tree, but ignores the BST property.
Time O(n) · Space O(h)
Approach 2: In-order traversal with early stop
An in-order traversal yields values in sorted order. Track the last value at or below the target, and stop at the first value above it; the answer is whichever of those two is closer. Can stop early, but still walks O(n) nodes when the target is large.
Time O(n) worst case · Space O(h)
Approach 3: Single descent from the root
- Set
best = root.valandnode = root. - While
nodeexists: if|node.val - target| < |best - target|, or the distances are equal andnode.val < best, setbest = node.val. - Move to
node.leftiftarget < node.val, otherwise tonode.right. - Return
best.
Only one root-to-leaf path is visited.
Time O(h), which is O(log n) for a balanced tree · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Visit every node | O(n) | O(h) |
| In-order traversal with early stop | O(n) worst case | O(h) |
| Single descent from the root | O(h), which is O(log n) for a balanced tree | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Closest Binary Search Tree Value solution in Python
def closest_value(root: Optional[TreeNode], target: float) -> int:
best = root.val
node = root
while node:
d, best_d = abs(node.val - target), abs(best - target)
if d < best_d or (d == best_d and node.val < best):
best = node.val
node = node.left if target < node.val else node.right
return bestClosest Binary Search Tree Value solution in JavaScript
function closestValue(root, target) {
let best = root.val;
let node = root;
while (node) {
const d = Math.abs(node.val - target);
const bestD = Math.abs(best - target);
if (d < bestD || (d === bestD && node.val < best)) best = node.val;
node = target < node.val ? node.left : node.right;
}
return best;
}Common mistakes
- Returning as soon as you reach a leaf without comparing the values seen higher up the path.
- Ignoring the tie rule, so a target exactly between two values returns the larger one.
- Rounding the target to an integer first. 1235.2 should return 1236, not 1234.
- Casting the target to an integer type in a typed language and losing the fractional part.
What interviewers look for
Say why one path is enough before you code it; interviewers want the argument, not just the loop. "Every node off the path is on the far side of a node on the path, so it can't be closer" is the key sentence.
Ask how ties should be broken, then show the extra comparison in your update. Mention that the cost is the tree height, so a skewed tree is still O(n).
Follow-up questions
What if you needed the k closest values?
Do an in-order traversal while keeping a window of k values: once the window is full, drop the front when the next value is closer than it, and stop when the next value is farther than the front. That is O(n) and O(k) space. With two stacks of predecessors and successors from the search path, you can get O(h + k).
What if the tree were a plain binary tree with no ordering?
You lose the pruning and have to visit every node, so it is O(n). The comparison and tie rule are the same.
How would you answer many queries quickly on a tree that never changes?
Flatten it once into a sorted array with an in-order traversal, then binary search each target and compare the neighbours on each side. Each query is O(log n) regardless of the tree's shape.
Companies that ask Closest Binary Search Tree Value
Closest Binary Search Tree Value is tagged by 89 companies in our interview dataset. The score shows how often it comes up at each company.
- Mphasis100%
- Murex100%
- Vanguard100%
- Jacobs97%
- Genpact96%
- Siriusxm93%
- Blackbaud89%
- Testlio85%
- Here Technologies84%
- Motorola Solutions84%
- Payactiv83%
- Apptio81%
- Allstate81%
- Weedmaps80%
- Broadcom80%
- Olympus80%
- Snap79.6%
- Verisk79%
- Seagate78%
- Kaseya78%
- Dicks Sporting Goods76%
- Boeing72%
- Trend Micro71%
- Iodine Software71%
and 65 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required