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

by



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.

a-binary-search-tree Teaching Kids Programming - Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) algorithms Binary Search Algorithm Depth First Search python Recursion teaching kids programming youtube video

A Binary Search Tree

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

Example 2:
Input: root = [1], 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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system

1063 words
Last Post: The Young Prompt Engineers





Source: Internet

Leave a Comment

We are offering free coding tuts

Got it!
X