Katkat
Back

Find the Closest Value in a Binary Search Tree

CoupangSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests your ability to traverse a binary search tree efficiently by leveraging its ordering property to find the node value closest to a given target number.

Problem Statement

Given the root of a non-empty Binary Search Tree (BST) and a target floating-point number target, return the value of the node in the BST that is closest to target.

You may assume that there is only one unique value in the BST that is closest to target.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def closest_value(root: TreeNode, target: float) -> int:
    pass

Input & Output Format

  • Input: root, the root node of a valid BST containing integer values; target, a floating-point number.
  • Output: An integer representing the node value with the minimum absolute difference abs(node.val - target).

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -10^9 <= Node.val <= 10^9
  • -10^9 <= target <= 10^9
  • There is guaranteed to be a unique closest value.

Examples

Example 1

Input: root = [4, 2, 5, 1, 3], target = 3.714286
       4
      / \
     2   5
    / \
   1   3
Output: 4
Explanation: The distances to target 3.714286 are:
|4 - 3.714286| = 0.285714
|3 - 3.714286| = 0.714286
Node 4 is the closest.

Example 2

Input: root = [1], target = 4.428571
Output: 1
Explanation: The tree has only one node, so 1 is the closest.

Edge Cases

  • The tree contains only a single node.
  • target is smaller than the minimum value or larger than the maximum value in the tree.
  • target is exactly equal to one of the node values.

Hints

Hint 1

Track the closest value seen so far as you traverse down the tree from the root.

Hint 2

At each node, compare the target with the current node's value to decide whether to explore the left subtree or the right subtree.

Hint 3

Because the tree is a BST, if target is less than the current node's value, any closer value must lie in the left subtree; otherwise, it must lie in the right subtree.

Follow-up questions

  • What is the time complexity in the worst case (e.g., a skewed tree), and how would an auto-balancing BST like an AVL or Red-Black tree change that?
  • How would you modify your solution if you were asked to return the `k` closest values instead of just one?
  • How can you implement this iteratively using `O(1)` auxiliary space without recursion?