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
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) —
loading...
Last Post: Reverse a Sentence (Sentence Reversal Algorithm)
Next Post: How to Exchange the Odd and Even Bits of a 32-bit Integer?