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

Question

Sample Input:

Sample Input: tree

Sample Output:

Solution

The main objective here is to find the closest number to the given target value.

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

public int value;
public BST left;
public BST right;
}
Access to Root node, left Node and right node.
Tree
  1. We will create a function that takes the currentTree, targetValue and the closestNode.
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.
  1. So if currentNodeValue > targetValue, Move Left.
  2. But if currentNodeValue < targetValue, Move Right.
  3. But if currentNodeValue == targetValue, that means the targetValue is actually present in our binary node. In that case return the value itself.
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?

Average Case:

Worst Case:

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;
}
}
}

Average Case:

Worst Case:

--

--

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