Closest Value in BST — Competitive Programming with Time and Space Complexity

Question

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.

Note: 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:

Tree is given as:

Sample Input: tree

target = 12

Sample Output:

13

Solution

public class BST
{
public BST(int value)
{
this.value = value;
}

public int value;
public BST left;
public BST right;
}

Now the above image shows the binary search tree, and the target value is 12.

Now the first node in the tree is 10, and we know that the value at right nodes must be greater than 10, and the value at left nodes must be less than 10. So to find the closest value to 12 (target value), we need to traverse towards right. Thus, in this way, we can eliminate half of the tree from traversing.

And at inital point, the root node will be considered as the closest node to 12. Thus, closest = 10.

Access to Root node, left Node and right node.
Tree
private int GetClosestValue(BST tree, int target, int closest){}
int answer = GetClosestValue(tree, 12, 10);
Traversing first Node
private int GetClosestValue(BST tree, int target, int closest)
{
if (Math.Abs(target - closest) > Math.Abs(target - tree.value))
{
closest = tree.value;
}
}
Deciding where to move further.
private int GetClosestValue(BST tree, int target, int closest)
{
if (Math.Abs(target - tree.value) < Math.Abs(target - closest))
{
closest = tree.value;
}
if (tree.value > target && tree.left != null)
{
return GetClosestValue(tree.left, target, closest);
}
else if (tree.value < target && tree.right != null)
{
return GetClosestValue(tree.right, target, closest);
}
else
{
return closest;
}
}

Time and Space Complexity?

Time complexity of binary search tree is O(log n).
Space complexity will also be O(log n). We are storing just one variable closest, but since it’a a recursion, thus the stack will be called again and again till O(log n) times, thus the space complexity is also O(log n).

Skewed Binary Tree. (Worst Case Scenario)
private int GetClosestValue(BST tree, int target, int closest)
{
// Time Complexity
// - Average Case: O(log n)
// - Worst Case: O(n)
// Space Complexity
// - Average Case: O(1)
// - Worst Case: O(1)
while (true)
{

if (Math.Abs(target - tree.value)<Math.Abs(target - closest))
{
closest = tree.value;
}
if (tree.value > target && tree.left != null)
{
tree = tree.left;
}
else if (tree.value < target && tree.right != null)
{
tree = tree.right;
}
else
{
return closest;
}
}
}

Time complexity of binary search tree is O(log n).
Space complexity is O(1).

Time complexity of binary search tree is O(n).
Space complexity is O(1).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store