How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at DoorDash during technical interviews.

Find closest value to a target in a BST | DoorDash Coding Question

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.

Input: ([2,1,3], 2.0)

Expected Output: 2

Explanation: Exact match at the root: distance 0 wins immediately.

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

Expected Output: 2

Explanation: 2 and 3 are both 0.5 away; the tie-break returns the smaller value, 2.

Input: ([10,5,15,2,7,None,18], 6.0)

Expected Output: 5

Explanation: Unbalanced subtree (15 has no left child). |5-6|=1 < |7-6|=1? equal -> tie -> smaller value 5. Both 5 and 7 are distance 1, so 5 wins.

Input: ([-5,-10,0], -7.5)

Expected Output: -10

Explanation: Negatives with an exact tie: -5 and -10 are each 2.5 from -7.5; the smaller value -10 is returned.

Input: ([8,4,12,2,6,10,14], 12.4)

Expected Output: 12

Explanation: Balanced tree; descending toward 12.4 lands on 12 (distance 0.4) over 14 (distance 1.6).

Hints

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.
Keep a running 'closest' value updated at every node you visit on the way down, including the root.
Handle the tie carefully: when |node - target| equals |closest - target|, prefer the smaller value to make the answer deterministic.

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.