Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Thinking Process

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Examples

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • 0 <= Node.val <= 10^9
  • -10^9 <= target <= 10^9

Algorithm Breakdown

Key Insight: BST Property Utilization

The algorithm uses BST property to narrow down the search:

  • If target < root->val:
    • Closest value is either in left subtree or root itself
    • Search left, then compare with root
  • If target > root->val:
    • Closest value is either root or in right subtree
    • Search right, then compare with root
  • If target == root->val:
    • Root is the closest (distance = 0)
    • Return root value

Closer Value Logic

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val
        node = root

        while node:
            if abs(node.val - target) < abs(closest - target):
                closest = node.val

            if target < node.val:
                node = node.left
            else:
                node = node.right

        return closest

This function determines which value is closer:

  • target - lower: Distance from lower to target
  • upper - target: Distance from target to upper
  • If upper - target >= target - lower: Lower is closer or equal → return lower
  • Otherwise: Upper is closer → return upper

Why this works:

  • When distances are equal, we prefer the smaller value (lower)
  • This handles the constraint: “If there are multiple answers, print the smallest”

Recursive Structure

The recursion follows this pattern:

  1. Base case: Leaf node or no appropriate subtree → return current value
  2. Recursive case:
    • Search appropriate subtree
    • Compare subtree result with current value
    • Return closer value

Complexity

Time Complexity: O(h)

  • h = height of tree
  • Best case (balanced BST): O(log n)
  • Worst case (skewed tree): O(n)
  • Each recursive call: O(1) work, traverse one path from root to leaf

Space Complexity: O(h)

  • Recursion stack: O(h) for recursive calls
  • Best case (balanced BST): O(log n)
  • Worst case (skewed tree): O(n)

Key Points

  1. BST Property: Leverage BST structure to search efficiently
  2. Recursive Search: Search appropriate subtree based on target comparison
  3. Compare Candidates: Always compare subtree result with current node
  4. Tie Breaking: When distances are equal, prefer smaller value
  5. Single Path: Only traverse one path from root to leaf (not entire tree)

Detailed Example Walkthrough

Example: root = [4,2,6,1,3,5,7], target = 3.5

BST:
        4
       / \
      2   6
     / \ / \
    1  3 5  7

Step 1: root = 4, target = 3.5
  4 > 3.5 → go left, recurse left subtree

Step 2: root = 2, target = 3.5
  2 < 3.5 → go right, recurse right subtree

Step 3: root = 3, target = 3.5
  3 < 3.5 → go right
  root->right == nullptr → return 3

Step 4: Back to root = 2
  Compare: closerValue(2, 3, 3.5)
  target - 2 = 1.5
  3 - target = 0.5
  1.5 > 0.5 → return 3

Step 5: Back to root = 4
  Compare: closerValue(3, 4, 3.5)
  target - 3 = 0.5
  4 - target = 0.5
  0.5 == 0.5 → return 3 (prefer smaller when equal)

Result: 3

Iterative Approach for Comparison

def closerValue(self, lower, upper, target):
    if abs(lower - target) <= abs(upper - target):
        return lower
    return upper

Comparison:

  • Iterative: O(1) space, simpler loop
  • Recursive: O(h) space, more intuitive structure
  • Both: O(h) time complexity

Edge Cases

  1. Single node: Return root value
  2. Target equals node value: Return that value (distance = 0)
  3. Target very large: Return maximum value in tree
  4. Target very small: Return minimum value in tree
  5. Two nodes equally close: Return smaller value (per constraints)

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Binary Search Tree, Tree, Recursion, Binary Search, Easy

Key Takeaways

  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.

References

Template Reference