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

Question — 6 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve an easy problem, Closest Value in BST.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Github Repository Link: Github/ClosestValueInBST

Go to the previous question → Question — 5 (Non-Constructible Change)

Go to the next question → Question — 7 (Branch Sums in Binary Tree)

Code Wrestling

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

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

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

So a simple solution would be to find the difference between target value and each value in BST, and return the value which has minimum difference.
But finding the difference with each element in the BST is definitely not a good solution. So let’s use some features of Binary Seach Tree.

Create a class BST:
Each BST node has an integer value, a left child node, and a right child node. And for each root node, the node at right is always greater than root node and the node at left is always less than root node.

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

Approach:

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.

Tree

We will traverse the BST, node by node, all the while keeping track of the node with the closest value to the target value. So here at each traversal, we have access to the node and the left node and the right node. That gives a hint to use Recursion.

So let’s try to code it out together.

1. We will create a function that takes the currentTree, targetValue and the closestNode.

private int GetClosestValue(BST tree, int target, int closest){
}

2. And when we will call this function, initially, tree will be our given tree, targetValue as 12, and closest = first node value, i.e, 10.

int answer = GetClosestValue(tree, 12, 10);

3. Now let’s proceed towards writing our function. So first we will always be keeping a track of our closest node. So for a given tree, we will find which is the closest node, as shown in below image:

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

4. After finding the current closest value, we have to decide that from now onwards should we move towards left or right? For that we will compare if the targetValue and currentNode value. (targetValue = 12)

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.

Thus the final solution is:

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:

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).

Worst Case:

Skewed Binary Tree. (Worst Case Scenario)

Suppose our tree looks like this, then:

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

Space complexity will also be O(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(n) times, thus the space complexity is also O(n).

We can definitely reduce our space complexity, if we use iteration instead of Recursion. Let me just show you below code:

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

Thus we are just iterating, and at last returning the closest Value (breaking the while loop). And we are just storing one variable i.e closest.

Thus the time and space complexity, goes like this:

Average Case:

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

Worst Case:

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

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.