Closest Binary Search Tree Value
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.
In a BST, every node's left subtree contains only smaller values and every right subtree only larger ones. This ordering means the search does not have to touch every node. If the target is less than the current node's value, no node in the right subtree can be closer than the current node itself, so that entire subtree can be skipped. The search can proceed like binary search on a sorted array.
Key Constraints:
1 <= number of nodes <= 10^4→ With up to 10,000 nodes, an O(n) traversal is acceptable, but the BST ordering allows an O(h) search along a single path.0 <= Node.val <= 10^9→ Distances are computed asdouble. Adoublerepresents integers exactly up to 2^53, far above 10^9, so subtracting an integer node value from the target loses no precision.-10^9 <= target <= 10^9→ The target can be negative even though node values are non-negative, and it is a floating-point number, so an exact match may not exist.
Approach 1: Inorder Traversal (Brute Force)
Intuition
Collect every value in the tree, then scan the list for the one with the minimum absolute difference from the target, keeping the smaller value on ties. An inorder traversal visits a BST's nodes in sorted order, though this approach only needs the values, not their order.
This treats the tree as a plain container and ignores its ordering during the search, so every node gets visited.
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
Tree [4, 2, 5, 1, 3] with target = 3.5. Both 3 and 4 sit at distance 0.5 from the target, so this input exercises the tie-breaking rule.
Code
- Time Complexity: O(n). The inorder traversal visits every node, and the scan reads the collected list once. Both steps are O(n).
- 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.
This visits every node even though comparing the target with a node's value already identifies the only subtree that can hold a closer candidate. The next approach uses that comparison to walk a single root-to-leaf path.
Approach 2: BST-Guided Search (Iterative)
Intuition
A BST supports the same navigation as binary search on a sorted array. At each node, compare the target to the node's value: if the target is smaller, move left; otherwise move right. Along the way, track the closest value seen so far.
This walk never backtracks, so it touches one node per level along a single root-to-leaf path.
When target < node.val, every value in the right subtree is at least node.val, so each of them sits farther above the target than node.val itself. Skipping the right subtree therefore discards no candidate better than the node already examined. The mirror argument applies when moving right.
Because the walk always steps toward the target, both the closest value below the target and the closest value above it (when they exist) appear on the root-to-null search path. The answer must be one of these two neighbors, and the update rule compares both: it keeps the nearer one, and on a tie it keeps the smaller, which matches the problem's tie-breaking requirement.
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
The same input, tree [4, 2, 5, 1, 3] with target = 3.5. The tie between 3 and 4 now resolves during the descent instead of in a separate scan.
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). The algorithm keeps a few scalar variables and uses no recursion stack or auxiliary data structures.
The same descent can also be written recursively, passing the running closest value down through the calls.
Approach 3: Recursive BST Search
Intuition
This is the same descent as Approach 2, written as a recursive function. Each call processes one node: update the closest value, then recurse into the child on the target's side of the current node. A null node ends the recursion and returns the best value found.
The recursive form trades the loop's O(1) space for a call stack that grows with the tree height.
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
Tree [4, 2, 5, 1, 3] with target = 3.714286, the input from Example 1. The root is already the closest value, so each deeper call leaves closest unchanged.
Code
- Time Complexity: O(h) where h is the height of the tree. As in Approach 2, the search visits one node per level along a single path.
- Space Complexity: O(h). The recursion stack holds one frame per level: O(log n) in a balanced tree and O(n) in a skewed one, compared with the iterative version's O(1).