Solution by pingu92

  • 0

    Approach #1 Recursive Tree Traversal [Accepted]


    Given tree is binary search tree (BST, read more here: 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.


    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.


    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)
                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.