Closest Binary Search Tree Value
Last Updated: March 29, 2026
Understanding the Problem
We have a binary search tree and a target value (which can be a decimal), and we need to find which node value is closest to that target. If two node values are equally close, we return the smaller one.
The BST property is the key here. In a BST, every node's left subtree contains only values smaller than the node, and every node's right subtree contains only values larger. This ordering means we don't need to check every single node. If the target is less than the current node, the answer can't be hiding in the right subtree (well, it could be the current node, but nothing further right will be closer). So we can prune our search, much like binary search on a sorted array.
Key Constraints:
1 <= number of nodes <= 10^4→ With up to 10,000 nodes, even an O(n) traversal is acceptable. But we can do better by leveraging the BST structure.0 <= Node.val <= 10^9→ Node values are non-negative and can be large. No overflow concerns in Java/C++ since we'll uselongordoublefor distance calculations.-10^9 <= target <= 10^9→ Target can be negative even though node values are non-negative. Also, the target is a floating-point number, so the closest node value might not be an exact match.
Approach 1: Inorder Traversal (Brute Force)
Intuition
The most straightforward idea is to collect all the values in the BST and then find which one is closest to the target. Since an inorder traversal of a BST gives us values in sorted order, we can traverse the entire tree, store every value, and then scan through the list to find the minimum absolute difference.
This ignores the BST structure for the search itself, essentially treating it as "give me all the values and I'll figure it out." It works, but it's wasteful because we're visiting every node when we don't have to.
Algorithm
- Perform an inorder traversal of the BST to collect all node values into a list.
- Iterate through the list and track the value with the smallest absolute difference from the target.
- If two values have the same difference, keep the smaller one.
- Return the closest value.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree during the inorder traversal, and then scan through the collected list once. Both operations are O(n), giving us O(n) overall.
- Space Complexity: O(n). We store all n node values in a list. The recursion stack also uses O(h) space where h is the tree height, but the list dominates.
We're visiting every single node even though the BST property tells us which direction to search. What if we walked down the tree like a binary search, only visiting one child at each level?
Approach 2: BST-Guided Search (Iterative)
Intuition
Here's the key insight: in a BST, we can navigate toward the target just like binary search navigates through a sorted array. At each node, we compare the target to the node's value. If the target is smaller, we go left. If it's larger, we go right. Along the way, we keep track of the closest value we've seen.
The beauty of this approach is that we never need to backtrack. At each node, the BST property guarantees that the subtree we skip can't contain a closer value than what we've already found on our path.
The correctness hinges on the BST property. When we decide to go left (because target < node.val), we discard the entire right subtree. Every value in the right subtree is greater than or equal to node.val. Since node.val is already farther from target in the "greater" direction, everything in the right subtree is even farther. The same logic applies in reverse when going right.
So at each level, we make the locally correct decision (go toward where the target would be), and we never skip over a potential answer. The closest value must lie on the path from the root to where the target would be inserted, and that's exactly the path we follow.
Algorithm
- Initialize
closestto the root's value. - Start at the root and walk down the tree.
- At each node, compare its value to the current closest. Update
closestif the current node is nearer to the target (or equally near but smaller). - If
target < node.val, move to the left child. Otherwise, move to the right child. - When we reach a null node, return
closest.
Example Walkthrough
Code
- Time Complexity: O(h) where h is the height of the tree. We follow a single path from root to a leaf. In a balanced BST, h = O(log n). In a skewed tree, h = O(n).
- Space Complexity: O(1). We only use a few variables. No recursion stack, no extra data structures.
This is the same algorithm expressed recursively, which some find more natural for tree problems.
Approach 3: Recursive BST Search
Intuition
This is the same algorithm as Approach 2, but expressed recursively. Some people find recursive tree code more natural to write, especially in interviews where you're already thinking about tree problems recursively.
The idea is identical: at each node, update the closest value, then recurse into the appropriate subtree. The recursion naturally stops when we hit a null node.
Algorithm
- Base case: if the node is null, return the current closest value.
- Compare the current node's value with
closestand update if it's nearer (or equally near but smaller). - If
target < node.val, recurse left. Otherwise, recurse right. - Return the result from the recursive call.
Example Walkthrough
Code
- Time Complexity: O(h) where h is the height of the tree. Same as Approach 2, we visit exactly one node per level.
- Space Complexity: O(h). The recursion stack holds one frame per level. In a balanced tree this is O(log n), in a skewed tree it's O(n). Worse than the iterative version's O(1).