Solution by pingu92


  • 0
    P

    Approach #1 Recursive Tree Traversal [Accepted]

    Intuition

    Given tree is binary search tree (BST, read more here: https://en.wikipedia.org/wiki/Binary_search_tree) that has a special property that left node has a value smaller than the root and right node has a value greater than the root.
    Our main task here is to limit the values of the tree in the given range defined by values L and R.

    Algorithm

    Suppose we have a function def trimBST(self, root, L, R):, we can recurse on the root. At any time if node.val < L we simply ignore this node and move to right subtree of the node. Similarly, at any time if node.val > R we ignore this node and move to left subtree of the node. If the value belongs in the range L < node.val < R then we recurse on both the subtree of the node.

    Python

    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if root is not None:
            if root.val > R: # ignore the right subtree
                return self.trimBST(root.left, L, R)
            elif root.val < L: # ignore the left subtree
                return self.trimBST(root.right, L, R)
            else:
                root.left = self.trimBST(root.left, L, R)
                root.right = self.trimBST(root.right, L, R)
                return root
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. Where n is the number of nodes in the tree.
      Since we traverse the entire tree just once, the complexity is $$O(n)$$.

    • Space complexity : $$O(n)$$ due to recursion.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.