Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Closest Binary Search Tree Value (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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. Among them, 6 is closer.

Example 2:

  • Input: Target: 25, Tree:
       20
     /    \
    10     30
  • Expected Output: 20
  • Justification: 20 and 30 are the closest numbers to 25. However, 20 is smaller than 30. So, 20 is selected as an output.

Example 3:

  • Input: Target: 2.9, Tree:
       2
     /   \
    1     3
  • Expected Output: 3
  • Justification: 3 is the closest value to 2.9 in the tree.

Constraints:

  • The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
  • 0 <= Node.val <= 10<sup>9</sup>
  • -10<sup>9</sup> <= target <= 10<sup>9</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible