Recursive Easy to Understand Verbose Solution

• 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;
}
}
}

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