medium Closest Binary Search Tree Value

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:

Code

Here is the code for this algorithm:

// Define a TreeNode structure with left and right children.
// class TreeNode {
//     int val;                  // Value stored in the node.
//     TreeNode left;            // Reference to the left child.
//     TreeNode right;           // Reference to the right child.

//     // Constructor to initialize a new node with a value.
//     TreeNode(int x) {
//         val = x;
//     }
// }

public class Solution {

  // This function finds the value in the BST closest to the target.
  public int closestValue(TreeNode root, double target) {
    // Initialize the closest value to the root's value.
    // This acts as a running minimum difference tracker.
    int closestVal = root.val;

    // Traverse the tree starting from the root.
    while (root != null) {
      // Check if the current node's value is closer to the target than the previous closest value.
      // If so, update closestVal.
      if (Math.abs(target - root.val) < Math.abs(target - closestVal)) {
        closestVal = root.val;
      } else if (Math.abs(target - root.val) == Math.abs(target - closestVal)) {
        closestVal = Math.min(closestVal, root.val);
      }

      // Decide the direction to traverse.
      // If the target is less than the current node's value, we move left; otherwise, move right.
      // This decision is made based on the properties of a BST.
      if (target < root.val) {
        root = root.left;
      } else {
        root = root.right;
      }
    }

    // Once we've traversed all possible paths, return the closest value.
    return closestVal;
  }

  // Main function to test the solution.
  public static void main(String[] args) {
    // Constructing a sample BST for testing.
    TreeNode example1 = new TreeNode(5);
    example1.left = new TreeNode(3);
    example1.left.left = new TreeNode(1);
    example1.left.right = new TreeNode(4);
    example1.right = new TreeNode(8);
    example1.right.left = new TreeNode(6);
    example1.right.right = new TreeNode(9);

    Solution solution = new Solution();

    // Test the closestValue function with the target value 6.4.
    System.out.println(solution.closestValue(example1, 6.4)); // Expected output: 6
  }
}

Complexity Analysis

• Time complexity: on average, because in a balanced BST, we'll typically only need to traverse down the height of the tree. In the worst-case scenario of a skewed tree, it will be .
• Space complexity: because we only use a constant amount of space to store the closestVal.