Solution Explanation for Closest Binary Search Tree Value

This problem asks to find the value in a Binary Search Tree (BST) that is closest to a given target value. If multiple values have the same minimum distance to the target, we return the smallest of these values.

We'll explore two solutions: a recursive approach and an iterative approach. Both leverage the properties of a BST to efficiently find the closest value.

Solution 1: Recursive Approach

This solution uses Depth-First Search (DFS) recursively to traverse the BST. The core idea is that, for any given node:

1. Check Closeness: We calculate the absolute difference between the current node's value and the target. This difference is compared to the current minimum difference (diff) found so far. If the new difference is smaller, or if it's equal but the current node's value is smaller than the current closest value (ans), we update ans and diff.

2. Navigate: Because it's a BST, we know that if the target is smaller than the current node's value, the closest value must lie in the left subtree. Otherwise, it's in the right subtree. This allows us to efficiently prune the search space.

3. Base Case: The recursion stops when we reach a null node (the end of a branch).

Time Complexity: O(H), where H is the height of the BST. In the worst case (a skewed tree), H can be equal to N (number of nodes), resulting in O(N) time complexity. In a balanced BST, H is log₂(N), leading to O(log₂(N)).

Space Complexity: O(H) in the worst case due to the recursive call stack. This is O(N) for a skewed tree and O(log₂(N)) for a balanced tree.

Solution 2: Iterative Approach

This approach achieves the same result without recursion, using a while loop. It's functionally equivalent to the recursive solution but avoids the overhead of recursive function calls.

1. Initialization: We initialize ans and diff with the root's value and a large initial difference, respectively.

2. Iteration: The loop continues as long as we haven't reached the end of a branch (root is not null). Inside the loop, we perform the same closeness check and update as in the recursive version.

3. Navigation: The next node to visit is determined in the same way as in the recursive solution, using the BST property to move to the left or right subtree.

4. Termination: The loop terminates when root becomes null, indicating that we've explored all relevant branches.

Time Complexity: O(H), same as the recursive approach. O(N) in the worst case and O(log₂(N)) for a balanced BST.

Space Complexity: O(1), because we use only a constant amount of extra space regardless of the tree size. This is a significant improvement over the recursive approach's space complexity.

Code Examples (Python)

Solution 1 (Recursive):

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        ans = root.val
        diff = float('inf')
 
        def dfs(node):
            nonlocal ans, diff
            if not node:
                return
            
            nxt = abs(node.val - target)
            if nxt < diff or (nxt == diff and node.val < ans):
                diff = nxt
                ans = node.val
 
            if target < node.val:
                dfs(node.left)
            else:
                dfs(node.right)
 
        dfs(root)
        return ans
 

Solution 2 (Iterative):

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        ans = root.val
        diff = float('inf')
        while root:
            nxt = abs(root.val - target)
            if nxt < diff or (nxt == diff and root.val < ans):
                diff = nxt
                ans = root.val
            
            if target < root.val:
                root = root.left
            else:
                root = root.right
        return ans

The iterative solution is generally preferred because of its better space complexity, making it more efficient for large BSTs. Both solutions demonstrate the same underlying algorithm, but the iterative approach is a more space-optimized implementation. The provided code examples include solutions in multiple languages for further reference.