Closest Binary Search Tree Value solution and explanation
Google
9 more videos on this problem
Closest Binary Search Tree Value || Leetcode 270 || Variant Question Big Tech Actually AsksCoding with Minmer · 20:20 · 6K views
Leetcode 270 Closest Binary Search Tree ValueRen Zhang · 7:09 · 4K views
LeetCode 270. Closest Binary Search Tree ValueHappy Coding · 8:45 · 3K views
Closest Binary Search Tree Value (Leetcode #270)Programmer Mitch · 10:49 · 2K views
LeetCode 270. Closest Binary Search Tree Value | Algorithm Easy Explanation and Drawing | Java CodeProgramming Life · 10:07 · 1K views
Microsoft Coding Interview Question | Leetcode 270 | Closest Binary Search Tree ValueWorkWithGoogler · 8:11 · 631 views
LeetCode 270. Closest Binary Search Tree Value | JSer - JavaScript & AlgorithmJSer · 5:51 · 561 views
Leetcode 270 : Closest Binary Search Tree Value | Programming With AshishProgramming With Ashish · 3:11 · 510 views
270. Closest Binary Search Tree Value in C# | LeetCode EasyInterviewPro · 10:58 · 399 views
Leetcode 270. Closest Binary Search Tree Value (Easy)The Leetcode Grind · 10:24 · 366 views
The problem
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.
# 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:
def dfs(node: Optional[TreeNode]):
if node is None:
return
nxt = abs(target - node.val)
nonlocal ans, diff
if nxt < diff or (nxt == diff and node.val < ans):
diff = nxt
ans = node.val
node = node.left if target < node.val else node.right
dfs(node)
ans = 0
diff = inf
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
private double target;
private double diff = Double.MAX_VALUE;
public int closestValue(TreeNode root, double target) {
this.target = target;
dfs(root);
return ans;
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
double nxt = Math.abs(node.val - target);
if (nxt < diff || (nxt == diff && node.val < ans)) {
diff = nxt;
ans = node.val;
}
node = target < node.val ? node.left : node.right;
dfs(node);
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int ans = root->val;
double diff = INT_MAX;
function<void(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) {
return;
}
double nxt = abs(node->val - target);
if (nxt < diff || (nxt == diff && node->val < ans)) {
diff = nxt;
ans = node->val;
}
node = target < node->val ? node->left : node->right;
dfs(node);
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} target
* @return {number}
*/
var closestValue = function (root, target) {
let ans = 0;
let diff = Infinity;
const dfs = node => {
if (!node) {
return;
}
const nxt = Math.abs(target - node.val);
if (nxt < diff || (nxt === diff && node.val < ans)) {
diff = nxt;
ans = node.val;
}
node = target < node.val ? node.left : node.right;
dfs(node);
};
dfs(root);
return ans;
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function closestValue(root: TreeNode | null, target: number): number {
let ans = 0;
let diff = Number.POSITIVE_INFINITY;
const dfs = (node: TreeNode | null): void => {
if (!node) {
return;
}
const nxt = Math.abs(target - node.val);
if (nxt < diff || (nxt === diff && node.val < ans)) {
diff = nxt;
ans = node.val;
}
node = target < node.val ? node.left : node.right;
dfs(node);
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestValue(root *TreeNode, target float64) int {
ans := root.Val
diff := math.MaxFloat64
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
nxt := math.Abs(float64(node.Val) - target)
if nxt < diff || (nxt == diff && node.Val < ans) {
diff = nxt
ans = node.Val
}
if target < float64(node.Val) {
dfs(node.Left)
} else {
dfs(node.Right)
}
}
dfs(root)
return ans
}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).
# 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:
ans, diff = root.val, inf
while root:
nxt = abs(root.val - target)
if nxt < diff or (nxt == diff and root.val < ans):
diff = nxt
ans = root.val
root = root.left if target < root.val else root.right
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int closestValue(TreeNode root, double target) {
int ans = root.val;
double diff = Double.MAX_VALUE;
while (root != null) {
double nxt = Math.abs(root.val - target);
if (nxt < diff || (nxt == diff && root.val < ans)) {
diff = nxt;
ans = root.val;
}
root = target < root.val ? root.left : root.right;
}
return ans;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int ans = root->val;
double diff = INT_MAX;
while (root) {
double nxt = abs(root->val - target);
if (nxt < diff || (nxt == diff && root->val < ans)) {
diff = nxt;
ans = root->val;
}
root = target < root->val ? root->left : root->right;
}
return ans;
}
};/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} target
* @return {number}
*/
var closestValue = function (root, target) {
let ans = root.val;
let diff = Infinity;
while (root) {
const nxt = Math.abs(root.val - target);
if (nxt < diff || (nxt === diff && root.val < ans)) {
diff = nxt;
ans = root.val;
}
root = target < root.val ? root.left : root.right;
}
return ans;
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function closestValue(root: TreeNode | null, target: number): number {
let ans = 0;
let diff = Number.POSITIVE_INFINITY;
while (root) {
const nxt = Math.abs(root.val - target);
if (nxt < diff || (nxt === diff && root.val < ans)) {
diff = nxt;
ans = root.val;
}
root = target < root.val ? root.left : root.right;
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestValue(root *TreeNode, target float64) int {
ans := root.Val
diff := math.MaxFloat64
for root != nil {
nxt := math.Abs(float64(root.Val) - target)
if nxt < diff || (nxt == diff && root.Val < ans) {
diff = nxt
ans = root.Val
}
if float64(root.Val) > target {
root = root.Left
} else {
root = root.Right
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursion | – |
| Iteration | – |
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 |
Frequently asked questions
Is Closest Binary Search Tree Value easy or hard?
Closest Binary Search Tree Value is categorized as an Easy problem. The challenge mainly involves recognizing that the BST ordering enables a binary-search-style traversal rather than scanning the entire tree.
Closest Binary Search Tree Value Python/Java solution
Both Python and Java implementations follow the same logic: maintain a variable storing the closest value and traverse the BST toward the target. At each node, update the closest candidate and move left or right based on comparison with the target. The algorithm runs in O(h) time and O(1) or O(h) space depending on whether iteration or recursion is used.
How to solve Closest Binary Search Tree Value in O(n)?
An O(n) solution performs a full traversal of the binary tree using DFS or BFS and compares every node value with the target. Track the smallest absolute difference encountered during traversal. This approach works for any binary tree but does not take advantage of the BST ordering.
What is the best approach for Closest Binary Search Tree Value?
The best approach uses the Binary Search Tree property to guide the search. Starting from the root, track the value with the smallest absolute difference from the target and move left or right depending on whether the target is smaller or larger than the current node. This reduces the search to O(h) time where h is the tree height, which is O(log n) for balanced BSTs.
Is Closest Binary Search Tree Value asked at Google/Amazon/Meta?
Binary Search Tree search problems like Closest Binary Search Tree Value frequently appear in interviews at companies such as Amazon, Google, and Meta. Interviewers use it to test understanding of BST properties, tree traversal, and efficient search strategies.
What data structure is used in Closest Binary Search Tree Value?
The primary data structure is a Binary Search Tree. The solution relies on its ordering property where left subtree values are smaller and right subtree values are larger than the parent node. Depth-first traversal or iterative binary search is used to navigate the tree efficiently.
What is the time complexity of Closest Binary Search Tree Value?
The optimized BST-based approach runs in O(h) time where h is the height of the tree. In a balanced Binary Search Tree, this becomes O(log n). In the worst case of a skewed tree, the height can reach n, resulting in O(n) time complexity.