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

1. Perform an inorder traversal of the BST, collecting all node values into a list.
2. The inorder traversal visits left subtree, then current node, then right subtree.
3. After collecting all values, iterate through the list to find the value with minimum absolute difference from the target.
4. Return that closest value.

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        def inorder(r: TreeNode):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        
        return min(inorder(root), key = lambda x: abs(target - x))

Time & Space Complexity

• Time complexity: $O(N)$
• Space complexity: $O(N)$

Where $N$ 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

1. Use an iterative inorder traversal with an explicit stack.
2. Keep track of the predecessor value (the last visited node smaller than or equal to target).
3. Go left as far as possible, pushing nodes onto the stack.
4. Pop from the stack to visit the current node.
5. If predecessor <= target < current value, compare both and return the closer one.
6. Update predecessor to current value and move to the right subtree.
7. 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 pred

Time & Space Complexity

• Time complexity: $O(k)$ in the average case and $O(H+k)$ in the worst case,
• Space complexity: $O(H)$

Where $k$ is an index of the closest element and $H$ 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

1. Initialize the closest value to the root's value.
2. 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.
3. Return the closest value found.

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val

        while root:
            closest = min(root.val, closest, key = lambda x: (abs(target - x), x))
            root = root.left if target < root.val else root.right

        return closest

Time & Space Complexity

• Time complexity: $O(H)$
• Space complexity: $O(1)$

Where $H$ 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 = val

Going 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.