Find Closest Value In BST

Tags

Find Closest Value In BST

Category

BST (Binary Search Trees)

Difficulty

Easy

Problem Statement

Given a Binary Search Tree (BST) and a target value, find the value in the BST that is closest to the target. You can assume there will be only one closest value.

Intuition

The BST property — left children are smaller, right children are larger — allows us to make an informed decision at each node about which subtree to explore. At each node, we update our closest value if the current node is nearer to the target, then move left if the target is smaller or right if the target is larger. This eliminates half the tree at each step, similar to binary search.

Approach

  1. Initialize closest to the root's value (or positive infinity).
  2. Start at the root. While the current node is not null:
    • If the absolute difference between the current node's value and the target is less than the absolute difference between closest and the target, update closest.
    • If the target is less than the current node's value, move to the left child.
    • If the target is greater than the current node's value, move to the right child.
    • If the target equals the current node's value, return the target (exact match found).
  3. Return closest.

Pseudocode

function findClosestValue(root, target):
    closest = root.value
    node = root
    while node is not null:
        if abs(target - node.value) < abs(target - closest):
            closest = node.value
        if target < node.value:
            node = node.left
        else if target > node.value:
            node = node.right
        else:
            return node.value
    return closest

Time & Space Complexity

  • Time: O(log n) on average for a balanced BST, O(n) in the worst case for a skewed BST.
  • Space: O(1) for the iterative approach. A recursive approach would use O(log n) average / O(n) worst-case stack space.

Key Insights

  • The BST property guides us toward the target efficiently — we never need to explore both subtrees.
  • An iterative approach is preferred over recursion since it uses constant space.
  • At each step, we only move in one direction, effectively halving the search space in a balanced tree.
  • An exact match allows immediate termination.

Edge Cases

  • Target is smaller than the smallest value in the BST: the closest value is the leftmost node.
  • Target is larger than the largest value in the BST: the closest value is the rightmost node.
  • Target matches a node's value exactly: return that value immediately.
  • BST with a single node: return the root's value.
  • When two values are equidistant from the target, the problem guarantees only one closest value.

Linked mentions