Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Closest Binary Search Tree Value (medium)

Problem Statement

Given a binary search tree (BST) and a target number, find a node value in the BST that is closest to the given target. If there are multiple answers, print the smallest.

A BST is a tree where for every node, the values in the left subtree are smaller than the node, and the values in the right subtree are greater.

Examples

Example 1:

  • Input: Target: 6.4, Tree:
       5
     /   \
    3     8
   / \   / \
  1   4 6   9
  • Expected Output: 6
  • Justification: The values 6 and 8 are the closest numbers to 6.4 in the tree

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Alex

· 3 years ago

[50,30,70,10,40,60,90]

closest: 55

Output 60

Expected 50

In mathematics, when a number is exactly in the middle of two others, as 55 is between 50 and 60, it's customary to round up. Therefore, 55 is considered closer to 60. The test case and provided solution is wrong.

Show 3 replies