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

target = 12

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.

`private int GetClosestValue(BST tree, int target, int closest){}`
`int answer = GetClosestValue(tree, 12, 10);`
`private int GetClosestValue(BST tree, int target, int closest){    if (Math.Abs(target - closest) > Math.Abs(target - tree.value))    {        closest = tree.value;    }}`
`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).

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