270. Closest Binary Search Tree Value
Model: qwen2.5-coder:14b
Topics: Binary Search,Tree
FAANG asked: 1
Acceptance rate: 50.3%
Problem Breakdown
The problem asks us to find the value in a Binary Search Tree (BST) that is closest to a given target value. The inputs are the root of the BST and the target value. The output should be the node value in the BST that minimizes the absolute difference between itself and the target.
Inputs:
root: The root node of the binary search tree.target: A floating-point number representing the target value.
Outputs:
- An integer value from the BST that is closest to the target.
Implicit Constraints or Edge Cases:
- The BST can have up to 10,000 nodes.
- Node values and the target can be as large as (10^9) in absolute terms.
- The tree could be unbalanced, but it will always be a valid BST (i.e., left child < parent < right child).
Intuition
A brute-force approach would involve traversing all nodes in the BST to find the one with the minimum absolute difference from the target. This would result in a time complexity of (O(n)), where (n) is the number of nodes, which is acceptable given the constraints.
However, we can leverage the properties of a binary search tree to improve our approach. Since the left subtree contains values less than the root and the right subtree contains values greater than the root, we can make informed decisions about which subtree to explore next based on the target value. This leads us to a more efficient solution with (O(h)) time complexity, where (h) is the height of the tree.
Approach
- Initialize Variables: Start by initializing
closest_valto the root’s value andmin_diffto the absolute difference between the root’s value and the target. - Traverse the Tree:
- Begin at the root node.
- At each node, update
closest_valif the current node’s value is closer to the target than the previously recorded closest value. - Compare the target with the current node’s value:
- If the target is less than the current node’s value, move to the left child (since all values in the right subtree are greater).
- If the target is greater than or equal to the current node’s value, move to the right child.
- Continue this process until you reach a leaf node (i.e., a node with no children).
- Return Result: Once traversal is complete,
closest_valwill hold the value in the BST that is closest to the target.
Complexity Analysis
- Time Complexity: (O(h)), where (h) is the height of the tree. In the worst case (unbalanced tree), this could be (O(n)). However, for a balanced tree, it would be (O(\log n)).
- Space Complexity: (O(1)) since we are using only a constant amount of extra space.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def closestValue(root: TreeNode, target: float) -> int:
closest_val = root.val
min_diff = abs(target - root.val)
current = root
while current:
if abs(target - current.val) < min_diff:
closest_val = current.val
min_diff = abs(target - current.val)
if target < current.val:
current = current.left
else:
current = current.right
return closest_val
Edge Cases Handled
- Single Node Tree: If the tree has only one node, that node’s value is returned as it is the only candidate.
- Target Value Greater than All Nodes: The algorithm will traverse to the rightmost node and return its value.
- Target Value Less Than All Nodes: The algorithm will traverse to the leftmost node and return its value.
- Balanced vs. Unbalanced Tree: The solution handles both cases efficiently, with time complexity depending on the height of the tree.
The provided solution is correct, efficient, and clear. It leverages the properties of a binary search tree to minimize unnecessary traversals, ensuring optimal performance.