Problem Statement

Given a binary search tree (BST) and a target number, find a node value in the BST that is closest to the given target. If there are multiple answers, print the smallest.

A BST is a tree where for every node, the values in the left subtree are smaller than the node, and the values in the right subtree are greater.

Examples

Example 1:

• Input: Target: 6.4, Tree:

       5
     /   \
    3     8
   / \   / \
  1   4 6   9

• Expected Output: 6
• Justification: The values 6 and 8 are the closest numbers to 6.4 in the tree. Among them, 6 is closer.

Example 2:

• Input: Target: 25, Tree:

       20
     /    \
    10     30

• Expected Output: 20
• Justification: 20 and 30 are the closest numbers to 25. However, 20 is smaller than 30. So, 20 is selected as an output.

Example 3:

• Input: Target: 2.9, Tree:

       2
     /   \
    1     3

• Expected Output: 3
• Justification: 3 is the closest value to 2.9 in the tree.

Constraints:

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

Solution

To solve the problem, initialize the closest value with the root node's value. Then, iteratively traverse the tree, comparing the target with the current node's value. If the target is closer to the current node than the closest value found so far, update the closest value. Depending on whether the target is greater or smaller than the current node's value, move to the right or left child, respectively. This process continues until all nodes are traversed.

Furthermore, we can leverage the properties of a BST. As we traverse the BST, we'll always choose the path that brings us closer to the target value. As we're doing so, we'll keep track of the closest node value we've encountered so far.

Step-by-Step Algorithm

1. Initialize the Closest Value:

   • Set the closest value (closestVal) to the root's value. This will store the value closest to the target as we traverse the tree.

2. Iterate Through the Tree:

   • Start from the root node and traverse the tree until a null node is reached.

3. Update the Closest Value:

   • For the current node:
     • Calculate the absolute difference between the target and the node's value.
     • If this difference is smaller than the difference between the target and closestVal, update closestVal to the current node's value.
     • Else if this difference is equal to the difference between the target and closestVal, update closestVal to the minimum of the closest value and current node's value, as we need to print the smallest answer if there are multiple answers.

4. Decide the Direction of Traversal:

   • Use the properties of the binary search tree:
     • If the target is less than the current node's value, move to the left child.
     • Otherwise, move to the right child.

5. Return the Closest Value:

   • Once all possible paths have been traversed, return closestVal as the closest value to the target.

Algorithm Walkthrough

Input:

• Tree:

         5
       /   \
      3     8
     / \   / \
    1   4 6   9
  

• Target: 6.4.

Steps:

1. Start at Root:

   • Current node: 5, closest value: 5.
   • Calculate the absolute difference:
     • |6.4 - 5| = 1.4.
   • Since 5 is the first value, closestVal = 5.

2. Traverse to the Right:

   • Target (6.4) is greater than 5, so move to the right child.
   • Current node: 8, closest value: 5.

3. Check Node 8:

   • Calculate the absolute difference:
     • |6.4 - 8| = 1.6.
   • 1.6 is larger than 1.4 = (|6.4 - 5|), so closestVal remains 5.

4. Traverse to the Left:

   • Target (6.4) is less than 8, so move to the left child.
   • Current node: 6, closest value: 5.

5. Check Node 6:

   • Calculate the absolute difference:
     • |6.4 - 6| = 0.4.
   • 0.4 is smaller than 1.4 = (|6.4 - 5|), so update closestVal = 6.

6. End Traversal:

   • Target (6.4) is greater than 6, so move to the right child.
   • Current node: null. End traversal.

7. Result:

   • The closest value to 6.4 is 6.

Output:

Closest Value: 6

Here is the visual representation of the algorithm: