Quick Overview

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.

Find closest value to a target in a BST

Company: DoorDash

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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`

Quick Answer: 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.

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 multiple values are equally close, return the **smaller** value. The tree is provided as a **level-order array** (LeetCode style): index 0 is the root, and for each non-null node its children appear next in breadth-first order. Use `None`/`null` for a missing child so the positions of later nodes stay correct. ### Input - `tree`: level-order array of node values (`None`/`null` marks a missing node) - `target`: a real number ### Output - An integer value from the BST that is closest to `target` (ties broken toward the smaller value) ### Example ``` tree = [4,2,5,1,3] (BST rooted at 4, left subtree {2,1,3}, right child 5) target = 3.714286 => 4 # |4 - 3.714| = 0.286 is smaller than |3 - 3.714| = 0.714 ``` ### Constraints - Number of nodes: `1 .. 10^5` - Node values are 32-bit signed integers - The tree is a valid BST but may be unbalanced

Constraints

  • 1 <= number of nodes <= 10^5
  • Node values are 32-bit signed integers
  • target is a real number within a reasonable range
  • The input is a valid BST but may be unbalanced
  • On equal distance, return the smaller value

Examples

Input: ([4,2,5,1,3], 3.714286)

Expected Output: 4

Explanation: Prompt example. |4 - 3.714| = 0.286 < |3 - 3.714| = 0.714, so 4 is closest.

Input: ([1], 4.428571)

Expected Output: 1

Explanation: Single-node tree: the only value is the answer regardless of target.

Hints

  1. Because the tree is a BST, you don't need to inspect every node: at each node, if target is smaller go left, otherwise go right.
  2. Keep a running 'closest' value updated at every node you visit on the way down, including the root.
  3. Handle the tie carefully: when |node - target| equals |closest - target|, prefer the smaller value to make the answer deterministic.

Loading coding console...