Help me in this easy trees problem

general
1

Hi, i am just starting out trees and not sure why am i getting a runtime error on this one.

class Solution {
public:
    TreeNode* findmin(TreeNode* root){
        if(root==NULL)
            return NULL;
        while(root->left!=NULL){
            root=root->left;
        }
        return root;
    }
    TreeNode* trimBST(TreeNode* root, int l, int r) {
        if(root==NULL) return root;
        else if(root->val>=l && root->val<=r){
         //   cout<<root->val<<" "<<l<<" "<<r<<endl;
            root->left=trimBST(root->left,l,r);
            root->right=trimBST(root->right,l,r);
            int flaf=1;
        }
        
        else{
           // cout<<"going to delete mr "<<root->val<<endl;
            //no child 
            if(root->left==NULL and root->right==NULL){
                delete root;
                root=NULL;
            }
            //1 child 
            else if(root->left==NULL){
                TreeNode* temp=root;
                root=root->right;
                delete temp;
            }
            else if(root->right==NULL){
                TreeNode* temp=root;
                root=root->left;
                delete temp;
            }
            //2 child 
            else{
                TreeNode* temp=findmin(root->right);
                root->val=temp->val;
                root->right=trimBST(root->right,l,r);
            }
        }
     return root;           
    }
};

It’s is showing error on this test case
[1,null,2]
2
4

2

comment this line or remove it.

I would suggest to do the same for this also.

Edit : If you stuck on LeetCode and facing runtime error then it will be helpful to use cerr instead of cout.

1 Like
3

This results in WA for

[2,1,3]
3
4

OUTPUT:

[3,1,3]

EXPECTED:

[3]

4

maybe this solution helps

1 Like
5

The link shows as 404, i saw some solutions but i was still not sure why mine throws an error

6

class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R)
{
if(root==NULL)
return NULL;
if(root->val >=L && root->val <=R)
{
if(root->left!=NULL)
root->left= trimBST(root->left,L,R);
if(root->right!=NULL)
root->right= trimBST(root->right,L,R);
return root;
}
if(root->val < L)
return trimBST(root->right,L,R);
return trimBST(root->left,L,R);

}
1 Like
7

Cool, but whats wrong in my approach…

8

I’ve solved around 100 problems on Trees in leetcode, and not once have I used the keyword delete. The delete keyword is simply not necessary while dealing with trees.

  1. root = NULL makes the tree size 0. (i.e all elements deleted).

  2. root = root->right deletes the root and the entire root->left subtree, there is no requirement to store the root in a temp pointer and delete it. Internally root->val is still stored in old address of root. But now that we have changed the address of root to root->right, the old value is simply forgotten.

Coming to your solution, for the input [2,1,3] the flow falls to the last if condition that you have written. temp is min(root->right) which eventually ends up becoming root->right.
Now root->val = temp->val which means your tree is now [3,1,3]. Finnally root->right = trimBST(root->right, 3, 4) which does no change to root->right, as the subtree is perfectly in range.

I’m attaching my solution, hope it helps. :v:

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);
        if(root->left)
            root->left=trimBST(root->left,L,R);
        if(root->right)
            root->right=trimBST(root->right,L,R);
        return root;        
    }
};

[EDIT] As for the runtime error I’m not very sure why, but I’m guessing it has something to with with the wrong use of the keyword delete or memory leak.

1 Like