Find closest value to a target in a BST

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

Find closest value to a target in a BST

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

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.