Trim a Binary Search Tree¶

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high].¶

The algorithm is recursive:¶
1) For a given node:¶
a) if the node is None just return it¶
b) if its val is lower than the lowest bound return the algo called on its right children¶
c) if its val is greater than the highest bound return the algo called on its left children¶
d) otherwise set its left children as the algo called on it and its right children as the algo call on it¶
In [ ]:
def trimBST(root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
    def helper(root, low, high):
        if not root:
            return(root)

        if root.val < low:
            return(helper(root.right, low, high))
        elif root.val > high:
            return(helper(root.left, low, high))
        else:
            root.left = helper(root.left, low, high)
            root.right = helper(root.right, low, high)
            return(root)

    return(helper(root, low, high))