C++ Solution 16ms (with intuition + explanation)


  • 0

    Intuition
    Recursively trim the left and right sides, and return the root.

    Edge Cases
    The edge cases are when the root itself falls outside the boundary. There are two possibilities: it falls out on the left side (root value is less than L) or it falls out on the right side (root value is greater than R). In these cases, we can just "promote" the opposite child up as the new root, after applying the recursive trimBST call on the child.
    Why can we do this? If the root value is less than L, then we know everything on the left side is also less than L by property of binary search tree; it follows that we can "throw away" everything on the left side. The same follows for the opposite case.

    Algorithm

        TreeNode* trimBST(TreeNode* root, int L, int R) {
            if (!root) return nullptr;
            if (root->val < L) return trimBST(root->right, L, R);
            if (root->val > R) return trimBST(root->left, L, R);
            root->left = trimBST(root->left, L, R);
            root->right = trimBST(root->right, L, R);
            return root;
        }
    

    Complexity Analysis
    This solution also short-circuits and makes sure we don't make 2 recursive calls when unnecessary.
    Regardless, in the worst case, we hit every node once, so we run in O(n) for n nodes in the tree.


Log in to reply
 

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