# Java solution, iteration version

• I just found everyone using recursion to solve this problem. And it's true that recursive solution is much clean and readable. But I just want to write a iterative version which is much longer. Using three loops, one for finding a new root. Second for removing the invalid nodes from left subtree of new root. The last one for removing the invalids nodes from right subtree of new root. Have fun with this solution. lol

``````class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return root;
}
//Find a valid root which is used to return.
while (root.val < L || root.val > R) {
if (root.val < L) {
root = root.right;
}
if (root.val > R) {
root = root.left;
}
}
TreeNode dummy = root;
// Remove the invalid nodes from left subtree.
while (dummy != null) {
while (dummy.left != null && dummy.left.val < L) {
dummy.left = dummy.left.right;
// If the left child is smaller than L, then we just keep the right subtree of it.
}
dummy = dummy.left;
}
dummy = root;
// Remove the invalid nodes from right subtree
while (dummy != null) {
while (dummy.right != null && dummy.right.val > R) {
dummy.right = dummy.right.left;
// If the right child is biggrt than R, then we just keep the left subtree of it.
}
dummy = dummy.right;
}
return root;
}
}
``````

• hahahahahahahahahahaha

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