Problem

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Examples

Example 1

graph TD;
D(4) --- B(2) & E(5)
B --- A(1) & C(3)
  
1
2

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

Solution

Method 1 - Recursion

A BST is structured such that for each node, the values in the left subtree are smaller, and those in the right subtree are larger. This allows us to decide whether to move left or right based on comparisons with the target.

Approach

  • Start from the root and traverse the BST.
  • Keep track of the current closest value ans while comparing the node value with the target.
  • If the target is less than the node’s value, move left; otherwise, move right.
  • At each step, update the closest value ans if the current node is closer to the target than the previously recorded closest value.
  • The traversal stops when we reach a leaf node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
 public int closestValue(TreeNode root, double target) {
	 return helper(root, target, Double.MAX_VALUE, root.val);
 }

 private int helper(TreeNode node, double target, double minDiff, int closest) {
	 if (node == null) {
		 return closest;
	 }

	 // Calculate the difference between current node's value and target
	 double diff = Math.abs(node.val - target);

	 // Update minDiff and closest if current node is closer
	 if (diff < minDiff) {
		 minDiff = diff;
		 closest = node.val;
	 }

	 // Recursively traverse left or right subtree
	 if (target < node.val) {
		 return helper(node.left, target, minDiff, closest);
	 } else if (target > node.val) {
		 return helper(node.right, target, minDiff, closest);
	 } else {
		 return node.val;  // If exact value is found, return immediately
	 }
 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        def helper(node: Optional[TreeNode], target: float, min_diff: float, closest: int) -> int:
            if not node:
                return closest

            # Calculate the difference between current value and target
            diff = abs(node.val - target)

            # Update min_diff and closest if current value is closer
            if diff < min_diff:
                min_diff = diff
                closest = node.val

            # Recursively traverse left or right subtree
            if target < node.val:
                return helper(node.left, target, min_diff, closest)
            elif target > node.val:
                return helper(node.right, target, min_diff, closest)
            else:
                return node.val  # If exact value is found, return immediately

        return helper(root, target, float('inf'), root.val)

Complexity

  • ⏰ Time complexity: O(h),where h is the height of the BST. In the best case (balanced BST), h = log(n), and in the worst case (skewed BST), h = n.
  • 🧺 Space complexity: O(h), due to the stack space needed for recursion. In the best case, h = log(n) for a balanced BST, and in the worst case, h = n for a skewed BST.

Method 2 - Iteration

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int closestValue(TreeNode root, double target) {
    double min = Double.MAX_VALUE;
    int ans = root.val;

    while (root != null) {

        double diff = Math.abs(root.val - target);
        if (diff < min) {
            min = Math.min(min, diff);
            ans = root.val;
        }
        if (target > root.val) {
            root = root.right;
        } else if (target < root.val) {
            root = root.left;
        } else {
            return root.val;
        }
    }

    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        min_diff: float = float('inf')
        ans: int = root.val

        while root:
            diff = abs(root.val - target)
            if diff < min_diff:
                min_diff = min(min_diff, diff)
                ans = root.val
            if target > root.val:
                root = root.right
            elif target < root.val:
                root = root.left
            else:
                return root.val
        
        return ans

Complexity

  • ⏰ Time complexity: O(h). where h is the height of the BST, same as recursive solution.
  • 🧺 Space complexity: O(1)