Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Binary Search, Tree, Depth-First Search, Binary Search Tree, Binary Tree
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.
- Examples
- Constraints
- Inorder Traversal
- Recursive Binary Search
- Iterative Binary Search
Examples
Input: root = [4,2,5,1,3], target = 3.714286
Output: 4
Input: root = [1], target = 4.428571
Output: 1
Constraints
The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^9
-10^9 <= target <= 10^9
Inorder Traversal
Intuition Traverse the entire BST using inorder traversal to get all values in sorted order, then find the value closest to target.
Steps
- Perform inorder traversal to collect all node values
- Iterate through values and track the closest to target
- Return the closest value found
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
values = []
def inorder(node):
if not node:
return
inorder(node.left)
values.append(node.val)
inorder(node.right)
inorder(root)
closest = values[0]
for v in values:
if abs(v - target) < abs(closest - target):
closest = v
return closest
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Simple but not optimal - visits all nodes even when answer is found early
Recursive Binary Search
Intuition Use BST property to navigate towards target while tracking the closest value seen so far.
Steps
- Initialize closest with root value
- Recursively traverse: go left if target < current node, else go right
- Update closest whenever we find a value closer to target
- Return closest value
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
closest = root.val
def dfs(node):
nonlocal closest
if not node:
return
if abs(node.val - target) < abs(closest - target):
closest = node.val
if target < node.val:
dfs(node.left)
else:
dfs(node.right)
dfs(root)
return closest
Complexity
- Time: O(h)
- Space: O(h)
- Notes: Uses recursion stack proportional to tree height
Iterative Binary Search
Intuition Same as recursive approach but uses iteration to avoid recursion stack overhead.
Steps
- Initialize closest with root value and current node as root
- While current node exists:
- Update closest if current node is closer to target
- Move left if target < current value, else move right
- Return closest value
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
closest = root.val
node = root
while node:
if abs(node.val - target) < abs(closest - target):
closest = node.val
if target < node.val:
node = node.left
else:
node = node.right
return closest
Complexity
- Time: O(h)
- Space: O(1)
- Notes: Optimal solution with constant space complexity