# Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm)

Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Example 1:
Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:
Input: root = , target = 4.428571
Output: 1

Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 10^9
-10^9 <= target <= 10^9

### Closest Binary Search Tree Value via Recursive Algorithm

We know it is trival to write a Recursion that looks for a target value in a Binary Search Tree. In a Balanced Binary Search Tree, the time complexity is O(H) where H is the height of the tree. Let’s review the code to find the exact value in a Binary Search Tree using Recursion:

 ```1 2 3 4 5 6 7 8 ``` ```def findInBST(root, T):     if not root:         return False     if root.val == T:         return True     if T < root.left:         return findInBST(root.left, T)     return findInBST(root.right, T)```
```def findInBST(root, T):
if not root:
return False
if root.val == T:
return True
if T < root.left:
return findInBST(root.left, T)
return findInBST(root.right, T)```

Similarly, with a slight modification, we can apply Recursion to find the closest node in the Binary Search Tree. The closest value must be the current node or in either its left or right subtree. We can pass a lambda function as the key to compute the distance to the min function.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:     def closestValue(self, root: Optional[TreeNode], target: float) -> int:         def dfs(root):             if not root:                 return inf             if target <= root.val:                 ans = dfs(root.left)             else:                 ans = dfs(root.right)             return min(ans, root.val, key=lambda x: abs(x - target))         return dfs(root)```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
def dfs(root):
if not root:
return inf
if target <= root.val:
ans = dfs(root.left)
else:
ans = dfs(root.right)
return min(ans, root.val, key=lambda x: abs(x - target))
return dfs(root)```

This is actually a Binary Search Algorithm, which can be converted to Iterative Binary Search, described at the end.

### Closest Binary Search Tree Value via Inorder Algorithm

We can traverse the Binary Search Tree. For example, if we perform an inorder (the Left Nodes, then current Node, and the Right Nodes), we will get a sorted list. The following uses a Recursion to perform an Inorder Traversal on a Binary Search Tree. It is a generator (iterator) that yields next larger Node in the Binary Search Tree.

Then, we can pass the iterator to the min functino, and also the key to obtain the min distance. However, the time complexity is still O(N) as all the nodes in the inorder will be checked to compare the closest Node.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:     def closestValue(self, root: Optional[TreeNode], target: float) -> int:         def dfs(root):             if not root:                 return             yield from dfs(root.left)             yield root.val             yield from dfs(root.right)                     return min(dfs(root), key=lambda x: abs(x - target))  ```

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
def dfs(root):
if not root:
return
yield from dfs(root.left)
yield root.val
yield from dfs(root.right)

return min(dfs(root), key=lambda x: abs(x - target))  ```

The space complexity is O(N) due to Recursion. An additional O(N) space will be required if we convert the Inorder to return a list instead of a yield.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:     def closestValue(self, root: Optional[TreeNode], target: float) -> int:         def dfs(root):             if not root:                 return []             ans = dfs(root.left)             ans += [root.val]             ans += dfs(root.right)             return ans                     return min(dfs(root), key=lambda x: abs(x - target))    ```

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
def dfs(root):
if not root:
return []
ans = dfs(root.left)
ans += [root.val]
ans += dfs(root.right)
return ans

return min(dfs(root), key=lambda x: abs(x - target))    ```

In the next lesson, we will improve this solution to O(K) so that we can return the min node once we have reached the two nodes A and B such as the Target falls between.

### Closest Binary Search Tree Value via Binary Search Algorithm

The first Recursion algorithm is actually Binary Search, which we can convert to the following Iterative Binary Search. The time complexity is O(H) where H is the height. The space complexity is O(1) constant.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, val=0, left=None, right=None): #         self.val = val #         self.left = left #         self.right = right class Solution:     def closestValue(self, root: Optional[TreeNode], target: float) -> int:         ans = root.val         while root:             ans = min(root.val, ans, key = lambda x: abs(target - x))             if target < root.val:                 root = root.left             else:                 root = root.right         return ans```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
ans = root.val
while root:
ans = min(root.val, ans, key = lambda x: abs(target - x))
if target < root.val:
root = root.left
else:
root = root.right
return ans```

GD Star Rating
a WordPress rating system

1063 words
Last Post: The Young Prompt Engineers

Source: Internet

We are offering free coding tuts

X