Recursive Easy to Understand Verbose Solution


  • 0
    M

    Space Complexity O(N) -> Worst case, binary tree in single line. Recursion will go as deep as number of nodes.
    Time Complexity O(N) -> Worst case, If all nodes are valid we will end up visiting each node.

    If node itself smaller than lower limit, we know the ensure left subtree of that node is in violation and we can trim right away. Similarly if node is in violation of upper limit, we can trim right subtree.

    If none of above, the node itself is valid and it can stay in the tree and we return as it is
    If the node is in violation, one of the non null left or right subtree will take its place. This is possible because of two observations below
    1) It can never be that node is in violation but both of its immediate nodes are not. At least one of them must be in violation as well
    leftSubtree <= node < rightSubtree
    2) If both subtree and node is in violation, we will end up returning null trimming the enture node and its subtree

    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if(root == null){return null;}
            
            // If node itself is smaller than lower boundary, all left subtree is in violation
            if(root.val < L){root.left = null;} // Trim entire left subtree
            root.left = trimBST(root.left, L, R);
    
            // If node itselfi s bigger than upper boundary, all right subtree is in violation
            if(root.val > R){root.right = null;} // Trim entire right subtree
            root.right = trimBST(root.right, L, R);
            
            if(root.val < L || root.val > R){
                return root.left != null ? root.left : root.right;
            }else{
                return root;
            }
        }
    }
    

Log in to reply
 

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