270. Closest Binary Search Tree Value - Detailed Explanation

Problem Statement

You are given the root of a binary search tree (BST) and a target value. Your task is to return the value in the BST that is closest to the target.

Examples

Example A

• Input: root = [4,2,5,1,3], target = 3.714286
• Output: 4
• Explanation: The BST contains the values 1, 2, 3, 4, and 5. The value 4 is the closest to 3.714286.

Example B

• Input: root = [1], target = 2.3
• Output: 1
• Explanation: There is only one node in the BST, so 1 is the closest by default.

Example C

• Input: root = [4,2,5,1,3], target = 0.1
• Output: 1
• Explanation: Among the values in the tree, 1 is the smallest and is closest to 0.1.

Constraints

• The number of nodes in the tree is at least 1.
• The BST property holds: for any given node, the left subtree contains values less than the node’s value and the right subtree contains values greater.
• The target is a floating point number.

Hints

• Hint 1: Remember that the BST property allows you to eliminate half of the remaining tree at each step. If the target is less than the current node’s value, you only need to search the left subtree; if it is greater, search the right.
• Hint 2: As you traverse the tree, keep track of the value that has the smallest difference from the target. Update this “closest” value when you find a node with a smaller difference.

Approaches

Brute Force Approach

Idea:
Traverse the entire tree (for example, using in-order or depth-first search) and compare every node’s value with the target. Keep a variable that tracks the closest value found so far.

Explanation:

• Visit every node.
• For each node, compute the absolute difference between the node’s value and the target.
• Update the closest value when a smaller difference is found.

Complexity:

• Time: O(n), where n is the number of nodes (since you visit every node).
• Space: O(n) in the worst case due to recursion (or stack) for an unbalanced tree.

Optimal Iterative Approach (Using BST Property)

Idea:
Utilize the BST properties to traverse the tree in a directed manner. Start at the root and move left or right depending on how the current node compares with the target.

Explanation:

• Initialize closest as the root’s value.
• While the current node is not null, update closest if the current node’s value is closer to the target than closest.
• If the target is less than the current node’s value, move to the left child; otherwise, move to the right child.
• This directed search avoids unnecessary comparisons by eliminating entire subtrees.

Complexity:

• Time: O(h) on average, where h is the height of the tree. In the worst case (skewed tree), it is O(n).
• Space: O(1) for the iterative solution.

Recursive Approach (Optimal Using BST Property)

Idea:
Similar to the iterative approach, but use recursion to traverse the tree.

Explanation:

• Define a recursive function that updates the closest value found so far.
• Compare the current node’s value with the target.
• Recursively search in the left subtree if the target is less than the current node’s value or in the right subtree if it is greater.
• Return the closest value after processing all relevant nodes.

Complexity:

• Time: O(h) on average.
• Space: O(h) due to the recursion call stack.

Step-by-Step Walkthrough and Visual Example

Consider the BST:

      4
     / \
    2   5
   / \
  1   3

For target = 3.714286 using the iterative approach:

• Start at 4:
  • Closest = 4, because |4 – 3.714286| ≈ 0.2857.
  • Since target < 4, move to the left subtree.
• At node 2:
  • Difference = |2 – 3.714286| ≈ 1.7143, which is not closer than 0.2857.
  • Since target > 2, move to the right subtree.
• At node 3:
  • Difference = |3 – 3.714286| ≈ 0.7143, still not better than 0.2857.
• Terminate:
  • No further nodes to explore.
• Result:
  • The closest value remains 4.

Common Mistakes

• Not Using BST Property:
  Traversing the entire tree even though the BST property allows you to eliminate large parts of the tree.

• Incorrect Update of Closest Value:
  Failing to update the closest value when a node with a smaller difference is encountered.

• Edge Case Neglect:
  Not handling cases when the tree has only one node.

Edge Cases

• Single Node Tree:
  The algorithm should immediately return the root’s value.

• Target Equal to a Node’s Value:
  The algorithm should return that node’s value without further traversal.

• Skewed Trees:
  In worst-case scenarios (e.g., all nodes in one branch), the time complexity becomes O(n).

Complexity Analysis Summary

• Brute Force Approach:

  • Time: O(n)
  • Space: O(n) (worst-case recursion or iterative storage)

• Optimal Iterative Approach:

  • Time: O(h) on average (worst-case O(n))
  • Space: O(1)

• Recursive Approach:

  • Time: O(h) on average
  • Space: O(h) due to recursion call stack

Python Code