Closest Binary Search Tree Value

EasyTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a non-empty binary search tree and a real number target. Return the node value in the tree whose distance to target (the absolute difference) is smallest. If two values are equally close to target, return the **smaller** of the two. All node values in the tree are distinct. Walking every node works in O(n), but the BST ordering lets you answer in O(h) time, where h is the height of the tree.

Examples

Input: root = [8,3,10,1,6,null,14], target = 6.8
Output: 6
6 is 0.8 away from the target, while the next-closest value, 8, is 1.2 away.
Input: root = [8,3,10,1,6,null,14], target = 9.0
Output: 8
Both 8 and 10 are exactly 1 away, so the smaller value wins.
Input: root = [2], target = -3.25
Output: 2
The only value in the tree is the answer.

Constraints

  • 1 <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^9
  • All node values are distinct
  • -10^9 <= target <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems