Teaching Kids Programming – Recursive Algorithm to Cut/Trim a Binary Search Tree


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary search tree root, an integer lo, and another an integer hi, remove all nodes that are not between [lo, hi] inclusive.

Constraints
n ≤ 100,000 where n is the number of nodes in root

cutting-a-binary-search-tree Teaching Kids Programming - Recursive Algorithm to Cut/Trim a Binary Search Tree algorithms python recursive teaching kids programming youtube video

Recursive Algorithm to Cut/Trim a Binary Search Tree

To trim a Binary Search Tree: There are three cases: First, when the root is below the lower threshold. Second, when the root is above the upper threshold. And third, the root is within the valid range.

For the first two cases, we should abandon the root together with corresponding branch. For the third case, we keep the root, and recursively deal with its left and right branch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBinarySearchTree(self, root, lo, hi):
        if root is None:
            return root
        if root.val < lo:
            return self.trimBinarySearchTree(root.right, lo, hi)
        if root.val > hi:
            return self.trimBinarySearchTree(root.left, lo, hi)
        # keep the root value, and deal with children recursively
        root.left = self.trimBinarySearchTree(root.left, lo, hi)
        root.right = self.trimBinarySearchTree(root.right, lo, hi)
        return root
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBinarySearchTree(self, root, lo, hi):
        if root is None:
            return root
        if root.val < lo:
            return self.trimBinarySearchTree(root.right, lo, hi)
        if root.val > hi:
            return self.trimBinarySearchTree(root.left, lo, hi)
        # keep the root value, and deal with children recursively
        root.left = self.trimBinarySearchTree(root.left, lo, hi)
        root.right = self.trimBinarySearchTree(root.right, lo, hi)
        return root

The time complexity is O(N) and space complexity is O(N) where N is the number of the nodes in the given binary search tree.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
396 words
Last Post: Reverse a Sentence (Sentence Reversal Algorithm)
Next Post: How to Exchange the Odd and Even Bits of a 32-bit Integer?

The Permanent URL is: Teaching Kids Programming – Recursive Algorithm to Cut/Trim a Binary Search Tree

Leave a Reply