Katkat
Back

Find closest value to a target in a BST

DoorDashMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of binary search tree properties and numeric approximation, measuring competence in tree traversal, comparison logic, and algorithmic efficiency under input-size constraints.

Problem

Given the root of a binary search tree (BST) and a floating-point number target, return the value in the BST that is closest to target.

If there are multiple values equally close, return the smaller value (or specify a deterministic tie-breaker).

Input

  • root: root node of a BST (each node has val, left, right)
  • target: a real number

Output

  • An integer value from the BST

Constraints

  • Number of nodes: 1 . 10^5
  • Node values are integers in a reasonable range (e.g., 32-bit signed)
  • Tree may be unbalanced

Example

BST values: [4,2,5,1,3], target = 3.714286 → output 4