Leetcode 270. Closest Binary Search Tree Value

Problem Statement

You are given a non-empty binary search tree (BST) and a target value, which is a floating point number. Your job is to find the value in the BST that's closest to the target value. This closest value is unique and it is guaranteed to exist in the BST.

A binary search tree (BST) is a binary tree where for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node.

Take the following example;

Example:

Input:

1The BST is:
2
3    4
4   / \
5  2   5
6 / \
71   3
8
9The target value is: 3.714286

Output:

1The closest value to the target in the BST is: 4

Explanation

A straightforward way to solve this problem is to use a recursive approach following these main steps:

1. If the current node is closer to the target than the current closest node, update the closest value.

2. If the target is less than the current node value, move to the left child node. Otherwise, move to the right child node.

3. Continue the above two steps until you reach a null node.

On each recursion, we calculate the absolute difference between the current node's value and the target, and compare it with the absolute difference of the closest value found so far.

In the given example, we first start at the root node 4. The absolute difference between 4 and 3.714286 is 0.285714. As we just started, this is the closest value we have so far. Since the target value is less than the current node value, we move to the left child node, which is 2. The absolute difference between 2 and 3.714286 is 1.714286, which is greater than the difference for the closest value we found earlier. Therefore, we do not update the closest value.

Since the target value is greater than the current node value, we move to the right child node, which is 3. The absolute difference between 3 and 3.714286 is 0.714286, which is also greater than the difference for the closest value we found earlier. Therefore, we do not update the closest value. As we cannot move further as both left and right child nodes of the current node are null, we stop the traversal and return the current closest value, which is 4.

Python Solution

1
2python
3class Solution:
4  def closestValue(self, root, target):
5    # If target < root, search left subtree
6    if target < root.val and root.left:
7      left = self.closestValue(root.left, target)
8      if abs(left - target) < abs(root.val - target):
9        return left
10
11    # If target > root, search right subtree
12    if target > root.val and root.right:
13      right = self.closestValue(root.right, target)
14      if abs(right - target) < abs(root.val - target):
15        return right
16
17    return root.val

Java Solution

Java Solution would convert in a similar manner to the Python solution provided.

1
2java
3public class Solution {
4  public int closestValue(TreeNode root, double target) {
5    if (target < root.val && root.left != null) { // target is less than root value, need to go left
6      int left = closestValue(root.left, target);
7      if (Math.abs(left - target) < Math.abs(root.val - target)) { // update closest node if left is closer to target
8        return left;
9      }
10    }
11    if (target > root.val && root.right != null) { // target is greater than root value, need to go right
12      int right = closestValue(root.right, target);
13      if (Math.abs(right - target) < Math.abs(root.val - target)) { // update closest node if right is closer to target
14        return right;
15      }
16    }
17    return root.val; // return root value if closest node not found on going left or right
18  }
19}

JavaScript Solution

1
2javascript
3class Solution {
4  closestValue(root, target) {
5    if(target < root.val && root.left) { // target is less than root value, need to go left
6      var left = this.closestValue(root.left, target);
7      if(Math.abs(left - target) < Math.abs(root.val - target)) { // update closest node if left is closer to target
8        return left;
9      }
10    }
11    if(target > root.val && root.right) { // target is greater than root value, need to go right
12      var right = this.closestValue(root.right, target);
13      if(Math.abs(right - target) < Math.abs(root.val - target)) { // update closest node if right is closer to target
14        return right;
15      }
16    }
17    return root.val; // return root value if closest node not found on going left or right
18  }
19}

C++ Solution

C++ Solution would translate in a similar manner as the Python solution provided.

1
2c++
3class Solution {
4public:
5    int closestValue(TreeNode* root, double target) {
6        if (target < root->val && root->left) { // target is less than root value, need to go left 
7            int left = closestValue(root->left, target);
8            if (abs(left - target) < abs(root->val - target)) { // update closest node if left is closer to target
9                return left;
10            }
11        }
12        if (target > root->val && root->right) { // target is greater than root value, need to go right
13            int right = closestValue(root->right, target);
14            if (abs(right - target) < abs(root->val - target)) { // update closest node if right is closer to target
15                return right;
16            }
17        }
18        return root->val; // return root value if closest node not found on going left or right
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int ClosestValue(TreeNode root, double target) {
5        if (target < root.val && root.left != null) { // target is less than root value, need to go left
6            var left = ClosestValue(root.left, target);
7            if (Math.Abs(left - target) < Math.Abs(root.val - target)) { // update closest node if left is closer to target
8                return left;
9            }
10        }
11        if (target > root.val && root.right != null) { // target is greater than root value, need to go right
12            var right = ClosestValue(root.right, target);
13            if (Math.Abs(right - target) < Math.Abs(root.val - target)) { // update closest node if right is closer to target
14                return right;
15            }
16        }
17        return root.val; // return root value if closest node not found on going left or right
18    }
19}

In every solution, if the target value is less than the root, we move left; if it's greater, we move right. If no closest node is found on going left or right, we return the root value. This process continues until we have traversed all the nodes or found the closest value.All of these solutions follow a similar logic and use recursion for the traversal of the binary search tree. It should be noted that although solutions are complete and seem simple, understanding them require knowledge of binary trees, recursion, as well as some programming concepts like classes, methods, and variables.

These solutions are the most efficient way to solve this problem. The time complexity is O(log N) because we are halving the problem size with each recursive call by ignoring the left or the right half of the tree. Thus, our time complexity is proportional to the height of the tree, which is logarithmic for a balanced binary search tree.

The space complexity of the solution is also O(log N), as at any point of time there are log N methods in the call stack, hence that much space is needed. This makes these solutions very efficient and practical to use, even for large data sets.

However, in some cases, we may also need to consider the possibility of an unbalanced binary search tree. In such a case, the time complexity could become O(N), where N is the number of nodes in the worst-case scenario.

In conclusion, whether the binary search tree is balanced or not plays a significant role in determining the efficiency of our solution. Despite the worst-case scenario possibility, these solutions still ensure that we are checking only the necessary nodes and avoid unnecessary calculations, making it the most optimal and practical solution to the problem.

One aspect we can improve in the future is the handling of edge cases and possible errors, such as empty trees, non-numeric node values or targets, etc. For now, the problem sets the precondition that the BST is non-empty and all values are numerical, so these cases are not accounted for in the current solutions.