Code Logo

BST Find Closest Value

Published at25 Jul 2026
Created by
Binary Search Tree Easy 1 views
Like0

Given an array representing a Binary Search Tree (BST) in level-order and a target value, find the value in the BST that is closest to the target. If there are multiple closest values, return the smaller one.

For example, in the BST [5, 3, 8, 1, 4, 7, 9] with target 6, the closest value is 5 (distance 1 vs 8's distance 2). With target 2, the closest is 3 (or 1; both are distance 1, so return the smaller: 1). An empty tree returns 0.

Finding the closest value in a BST is a classic search problem that leverages the BST property to efficiently narrow down the search space. At each node, the target is compared with the current node's value. If the target is smaller, the closest value must be in the left subtree; if larger, in the right subtree. The difference from standard search is that even if the target is not found, the closest value encountered during traversal is tracked.

For the array-based representation, start at index 0. Maintain a variable tracking the closest value found so far. At each node, update the closest if the current node is closer to the target than the previous closest. If the target is smaller than the current node, move left (2i+1); if larger, move right (2i+2). Continue until the index goes out of bounds.

Edge cases include an empty tree (return 0), a target value exactly equal to a node (return that node), and a target smaller than all nodes or larger than all nodes (return the minimum or maximum respectively).

Example Input & Output

Example 1
Input
[10,20,30,40,50],25
Output
20
Explanation

Closest to 25 is 20

Example 2
Input
[],10
Output
-1
Explanation

Empty

Example 3
Input
[5],5
Output
5
Explanation

Single node match

Example 4
Input
[1,2,3,4,5],3
Output
3
Explanation

3 exists, closest is itself

Example 5
Input
[1,3,5,7],6
Output
5
Explanation

Closest to 6 is 5 or 7, return 5

Algorithm Flow

Recommendation Algorithm Flow for BST Find Closest Value

Solution Approach

Traverse the BST while tracking the closest value seen so far.

function solution(arr, target) {
  if (arr.length === 0) return 0;
  var closest = arr[0], i = 0;
  while (i < arr.length) {
    if (Math.abs(arr[i] - target) < Math.abs(closest - target)) closest = arr[i];
    if (arr[i] < target) i = 2 * i + 2;
    else if (arr[i] > target) i = 2 * i + 1;
    else return arr[i];
  }
  return closest;
}

Initialize closest to the root value. At each node, update closest if the current node is closer to the target than the previous closest. If the target equals the current node, return it immediately. Otherwise, move left or right based on comparison.

Time complexity is O(log n) for balanced trees, O(n) worst case. Space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums, int t) {
        if(nums.length==0)return -1;int c=nums[0];
        for(int i=1;i<nums.length;i++){if(Math.abs(nums[i]-t)<Math.abs(c-t))c=nums[i];}
        return c;
    }
}