# Java solution, 6 liner

• ``````class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;

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

• I wrote 72 lines for this question....

``````public class Solution
{
public TreeNode TrimBST(TreeNode root, int L, int R)
{

var result = DFS(head, L, R);

}

private TreeNode FindHead(TreeNode root, int lower, int upper)
{
if (root == null) return null;

if (lower <= root.val && root.val <= upper)
{
return root;
}
else
{
if (root.val < lower)
{
}
else // root.val > upper
{
}
}
}

private TreeNode DFS(TreeNode root, int lower, int upper)
{
if (root == null) return null;

if (lower > root.val || root.val > upper)
{
}

if (newHead == null) return null;

{
{
}
else
{
}
}

{
{
}
else
{
}
}

}
}
``````

• @bacon I feel you. Happens with me, too! :|

• @bacon This is awkward, dude!

I wrote only 40 lines then got it solved!

• ``````class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val < L) {
return trimBST(root.right, L, R);
}
else if (root.val > R) {
return trimBST(root.left, L, R);
}
// maybe here can improve ?
root.left = trimBST(root.left, L, root.val);
root.right = trimBST(root.right, root.val, R);
return root;
}
}

``````

• SHAWN GOD!
(´ ͡༎ຶ ͜ʖ ͡༎ຶ `)

• Great idea! I write into C++ and Python :)

C++ solution:

``````class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if(!root) return root;
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;
}
};
``````

Python solution:

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

• @YangFan You overlooked three spaces you could remove to make it even harder to read.

• @ManuelP Yes, you're right, I overlooked three spaces. Just corrected. Thanks for pointing it out.

• @YangFan Hmm, actually you didn't remove them but instead added three more.

• @ManuelP It seems easier to read :p. Anyway, thank you for pointing out my careless mistake.

• @YangFan doesn't just replacing the left/right nodes cause memory leaks?

• @shawngao 不加判读不会出现null pointer？

• @bacon @realhly88 dude! its my 27 lines awkward version.

``````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);
}
TreeNode dummy = root;
while (dummy != null) {
while (dummy.left != null && dummy.left.val < L) {
dummy.left = dummy.left.right;
}
dummy = dummy.left;
}
dummy = root;
while (dummy != null) {
while (dummy.right != null && dummy.right.val > R) {
dummy.right = dummy.right.left;
}
dummy = dummy.right;
}
return root;
}
}
``````

• @FF_Ti Much better than mine.

• @bacon Thanks dude, I just abandon the recursive part and rewrite it into purely awkward iterative version. lol

``````class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return root;
}
while (root.val < L || root.val > R) {
if (root.val < L) {
root = root.right;
}
if (root.val > R) {
root = root.left;
}
}
TreeNode dummy = root;
while (dummy != null) {
while (dummy.left != null && dummy.left.val < L) {
dummy.left = dummy.left.right;
}
dummy = dummy.left;
}
dummy = root;
while (dummy != null) {
while (dummy.right != null && dummy.right.val > R) {
dummy.right = dummy.right.left;
}
dummy = dummy.right;
}
return root;
}
}
``````

• @wavy Could you explain " if (root.val < L) return trimBST(root.right, L, R);" for me, I mean why "root.right" when "root.val < L", thank you very much if you reply to me

• @AZe If current node value less than L, we only need to process its right child tree. Because its right child could possible have valid value.

• What is the Time Complexity of this code?

• @Shilpita We must visit every node once...so O(N); where N is the number of nodes in our tree

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