Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Closest Binary Search Tree Value

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
T

traviswlilleberg

· 9 months ago

When I run my code against the extended test cases I get a failure on the first test, [4,2,6,1,3,5,7].

It says expected is 4 for that answer, however the instructions state to use the smaller number so the expected should be 3.

Here's the output verbatim:

[4,2,6,1,3,5,7]

3.5

[8,3,10,1,6,null,14]

4.4

[5,3,8,1,4,6,9]

7.4

Output

3

3

8

Expected

4

3

8

Show 1 reply
V

Viktor

· 2 months ago

// Check if the current node's value is closer to the target than the previous closest value.
// If so, update closest_val.
if (std::abs(target - root->val) < std::abs(target - closest_val)) {
  closest_val = root->val;
} else if(std::abs(target - root->val) < std::abs(target - closest_val)){
  closest_val = std::min(closest_val,root->val);
}

It seems that the 2nd if should read as std::abs(target - root->val) == std::abs(target - closest_val), Otherwise, it's identical to the former condition.