Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Search Tree (BST) properties - Understanding that left subtree values are smaller and right subtree values are larger than the root
- Tree traversal techniques - Specifically inorder traversal which produces sorted values in a BST
- Binary search - Using BST structure to efficiently narrow down the search space
- Stack-based iteration - Converting recursive tree traversal to iterative using an explicit stack
1. Recursive Inorder + Linear search, O(N) time
Intuition
An inorder traversal of a BST produces values in sorted order. By collecting all values first, we can then find the one closest to the target using a simple linear search. While not the most efficient approach, it clearly demonstrates the relationship between inorder traversal and sorted order.
Algorithm
- Perform an inorder traversal of the BST, collecting all node values into a list.
- The inorder traversal visits left subtree, then current node, then right subtree.
- After collecting all values, iterate through the list to find the value with minimum absolute difference from the target.
- Return that closest value.
Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the total number of nodes in the binary tree
2. Iterative Inorder, O(k) time
Intuition
Since inorder traversal gives sorted values, we can stop early once we find the first value greater than or equal to the target. At that point, the answer is either the current value or the previous value we visited (the predecessor). This avoids traversing the entire tree when the target is small.
Algorithm
- Use an iterative inorder traversal with an explicit stack.
- Keep track of the predecessor value (the last visited node smaller than or equal to target).
- Go left as far as possible, pushing nodes onto the stack.
- Pop from the stack to visit the current node.
- If
predecessor <= target < current value, compare both and return the closer one. - Update predecessor to current value and move to the right subtree.
- If the loop ends, return the predecessor (target is larger than all values).
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
stack, pred = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if pred <= target and target < root.val:
return min(pred, root.val, key = lambda x: abs(target - x))
pred = root.val
root = root.right
return predTime & Space Complexity
- Time complexity: in the average case and in the worst case,
- Space complexity:
Where is an index of the closest element and is the height of the tree.
3. Binary Search, O(H) time
Intuition
The BST property allows us to use binary search. At each node, we compare the target with the current value to decide whether to go left or right. We track the closest value seen so far. If the target is smaller, we go left (there might be a closer smaller value). If the target is larger, we go right (there might be a closer larger value). This approach only visits nodes along a single path from root to leaf.
Algorithm
- Initialize the closest value to the root's value.
- While the current node is not null:
- If the current value is closer to target than the current closest (or equally close but smaller), update closest.
- If target < current value, move to the left child.
- Otherwise, move to the right child.
- Return the closest value found.
Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the height of the tree.
Common Pitfalls
Not Handling Tie-Breaking Correctly
When two values have the same distance to the target, the problem requires returning the smaller value. Using < instead of <= in the comparison can return the wrong answer.
# Wrong: Returns larger value on ties
if abs(val - target) < abs(closest - target):
closest = val
# Correct: Prefer smaller value on ties
if abs(val - target) < abs(closest - target) or \
(abs(val - target) == abs(closest - target) and val < closest):
closest = valGoing the Wrong Direction in BST
Choosing the wrong child based on comparison with target defeats the purpose of binary search. If target is smaller than current value, you must go left (not right) to find potentially closer smaller values.