Solution by awice

  • 0

    Approach #1: Recursion [Accepted]


    Let trim(node) be the desired answer for the subtree at that node. We can construct the answer recursively.


    When node.val > R, we know the trimmed binary tree must occur to the left of the node. Similarly, when node.val < L, the trimmed binary tree occurs to the right of the node. Otherwise, we will trim both sides of the tree.


    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null) return root;
            if (root.val > R) return trimBST(root.left, L, R);
            if (root.val < L) return trimBST(root.right, L, R);
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;


    class Solution(object):
        def trimBST(self, root, L, R):
            def trim(node):
                if not node:
                    return None
                elif node.val > R:
                    return trim(node.left)
                elif node.val < L:
                    return trim(node.right)
                    node.left = trim(node.left)
                    node.right = trim(node.right)
                    return node
            return trim(root)

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of nodes in the given tree. We visit each node at most once.

    • Space Complexity: $$O(N)$$. Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.

Log in to reply

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