Nearest Value in a Search Tree

Easy

A warehouse keeps its bin numbers in a binary search tree: every node has only smaller numbers in its left subtree and only larger ones in its right subtree. You get the root root and a number goal, which may be fractional. Return the bin number in the tree that is closest to goal. If two numbers are equally close (one below goal, one above), return the smaller one. Walking the whole tree works, but try to use its ordering and follow a single path down from the root.

Example 1

root=tree_node([20, 9, 31, 4, 15]), goal=17.4 → 15

15 is the closest to 17.4: it is 2.4 away, while 20 is 2.6 away.

Example 2

root=tree_node([20, 9, 31, 4, 15]), goal=25.5 → 20

20 and 31 are both 5.5 away from 25.5, a tie, so the smaller one, 20, wins.

Example 3

root=tree_node([7]), goal=-3.0 → 7

Constraints

The tree has between 1 and 10⁴ nodes
0 ≤ Node.val ≤ 10⁹, all values distinct
The tree is a valid search tree
-10⁹ ≤ goal ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Search Binary Tree

Similar problems

Pair Across Two Search Trees Medium Floor and Ceiling in a Search Tree Medium Most Frequent Values in a Search Tree Easy Pair Sum in a Search Tree Easy Closest Pair in a Search Tree Easy

Input

root=tree_node([20, 9, 31, 4, 15]), goal=17.4

Expected

Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.