ūüĎč
Welcome to my blog!

Find Closest Value in BST

Perfect your ability to find the closest value to a given number in a Binary Search Tree.

Find Closest Value in BST
BST
easy

Published At

6/4/2021

Reading Time

~ 3 min read

Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the closest value to that target value contained in the BST.

You can assume that there will only be one closest value.

Each BST node has an integer value, a left child node, and a right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null.

Sample Input

jstree =   10
       /     \
      5      15
    /   \   /   \
   2     5 13   22
 /           \
1            14
target = 12
jstree =   10
       /     \
      5      15
    /   \   /   \
   2     5 13   22
 /           \
1            14
target = 12

Sample Output

js13
js13

Hints

Hint 1

Try traversing the BST node by node, all the while keeping track of the node with the value closest to the target value. Calculating the absolute value of the difference between a node's value and the target value should allow you to check if that node is closer than the current closest one.

Hint 2

Make use of the BST property to determine what side of any given node has values close to the target value and is therefore worth exploring.

Hint 3

What are the advantages and disadvantages of solving this problem iteratively as opposed to recursively?

Optimal Space & Time Complexity

Average: O(log(n)) time | O(1) space - where n is the number of nodes in the BST Worst: O(n) time | O(1) space - where n is the number of nodes in the BST

Solution-1
jsfunction findClosestValueInBst(tree, target) {
	return findClosestValueHelper(tree, target, tree.value)
}
 
function findClosestValueHelper(tree, target, closest) {
	if (tree === null) return closest;
	
	if(Math.abs(target - closest) > Math.abs(target - tree.value)) {
		closest = tree.value
	}
	
	if (target < tree.value) {
		return findClosestValueHelper(tree.left, target, closest)
	} else if (target > tree.value) {
		return findClosestValueHelper(tree.right, target, closest)
	} else {
		return closest;
	}
}
 
// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-1
jsfunction findClosestValueInBst(tree, target) {
	return findClosestValueHelper(tree, target, tree.value)
}
 
function findClosestValueHelper(tree, target, closest) {
	if (tree === null) return closest;
	
	if(Math.abs(target - closest) > Math.abs(target - tree.value)) {
		closest = tree.value
	}
	
	if (target < tree.value) {
		return findClosestValueHelper(tree.left, target, closest)
	} else if (target > tree.value) {
		return findClosestValueHelper(tree.right, target, closest)
	} else {
		return closest;
	}
}
 
// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

ūüߣ

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek ūüôŹ

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.