Closest Binary Search Tree Value - Solution & Explanation
Problem Statement
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4
Example 2:
Input: root = [1], target = 4.428571 Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 109-109 <= target <= 109
Approach Overview
Problem Overview: Given the root of a Binary Search Tree and a floating-point target value, return the node value in the tree that is numerically closest to the target. The key advantage comes from the BST ordering property, which lets you eliminate half of the tree at each step.
Approach 1: Recursive BST Traversal (O(h) time, O(h) space)
This method performs a depth-first search while leveraging the Binary Search Tree property: left subtree values are smaller and right subtree values are larger than the current node. Maintain a variable closest that stores the value with the smallest absolute difference from the target. At each node, compare abs(node.val - target) with the current best and update if necessary. Then choose the next subtree: move left if target < node.val, otherwise move right. Because you only follow one branch at each step, the traversal behaves like binary search on the tree. Time complexity is O(h), where h is the tree height, and space complexity is O(h) due to the recursion stack. This approach fits naturally when implementing recursive depth-first search on a binary search tree.
Approach 2: Iterative Binary Search on BST (O(h) time, O(1) space)
The iterative version follows the exact same logic but avoids recursion. Start from the root and track the current best candidate in a variable closest. For each node, update the candidate if the absolute difference with the target is smaller than the previous best. Then move to either the left or right child depending on the BST ordering rule. Because only one path from root to leaf is explored, the traversal resembles classic binary search. The time complexity remains O(h), which is O(log n) for balanced trees and O(n) in the worst case of a skewed tree. Space complexity improves to O(1) since no recursion stack is used.
Recommended for interviews: Interviewers expect you to recognize and exploit the Binary Search Tree property. A naive full traversal would take O(n), but using the BST ordering reduces the search to O(h). Start by explaining that you keep track of the closest value while traversing the path determined by the target. The iterative solution is usually preferred because it avoids recursion overhead and demonstrates clear understanding of BST-based binary search.
Approach 1: Recursion
We define a recursive function dfs(node), which starts from the current node node and finds the node closest to the target value target. We can update the answer by comparing the absolute difference between the current node's value and the target value. If the target value is less than the current node's value, we recursively search the left subtree; otherwise, we recursively search the right subtree.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary search tree.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Approach 2: Iteration
We can rewrite the recursive function in an iterative form, using a loop to simulate the recursive process. We start from the root node and check whether the absolute difference between the current node's value and the target value is less than the current minimum difference. If it is, we update the answer. Then, based on the size relationship between the target value and the current node's value, we decide to move to the left subtree or the right subtree. The loop ends when we traverse to a null node.
The time complexity is O(n), where n is the number of nodes in the binary search tree. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursion | — |
| Iteration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive BST Traversal | O(h) | O(h) | Good when writing DFS-style code or when recursion improves readability |
| Iterative Binary Search on BST | O(h) | O(1) | Preferred for interviews and memory-constrained scenarios |
| Full Tree Traversal (Brute Force) | O(n) | O(h) | When the tree is not guaranteed to follow BST ordering |
Video Solution
Closest Binary Search Tree Value || Leetcode 270 || Variant Question Big Tech Actually Asks • Coding with Minmer • 6,059 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Closest Binary Search Tree Value easy or hard?
Closest Binary Search Tree Value Python/Java solution
How to solve Closest Binary Search Tree Value in O(n)?
What is the best approach for Closest Binary Search Tree Value?
Is Closest Binary Search Tree Value asked at Google/Amazon/Meta?
What data structure is used in Closest Binary Search Tree Value?
What is the time complexity of Closest Binary Search Tree Value?
Ready to solve this problem?
Practice Closest Binary Search Tree Value with our built-in code editor and test cases.
Practice on FleetCode