C++, recursion


  • 9
    Z

    The code works as recursion.

    If the root value in the range [L, R]
          we need return the root, but trim its left and right subtree;
    else if the root value < L
          because of binary search tree property, the root and the left subtree are not in range;
          we need return trimmed right subtree.
    else
          similarly we need return trimmed left subtree.
    

    Without freeing memory

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

    Free the memory
    As @StefanPochmann pointed out, it works well to delete only non-root nodes of the whole tree. His solution is as below. Thanks.

    TreeNode* trimBST(TreeNode* root, int L, int R, bool top=true) {
        if (!root)
            return root;
        root->left = trimBST(root->left, L, R, false);
        root->right = trimBST(root->right, L, R, false);
        if (root->val >= L && root->val <= R)
            return root;
        auto result = root->val < L ? root->right : root->left;
        if (!top)
            delete root;
        return result;
    }
    

  • 1
    A

    @zestypanda : Are we not supposed to explicitly delete the nodes? How would you handle that problem using recursion?


  • 0
    E

    My code is totally the same as yours 2333


  • 0
    E

    @asharboys The nodes are in fact not deleted, because we didn't use delete. However, it doesn't affect the final result.


  • 0
    A

    @Eagleming : Yes, I got that part, and I also understand that the final result will not be affected. I was under the assumption that in this problem, we are supposed to explicitly delete those nodes such that there are no dangling nodes left behind. In real-world, wouldn`t it be better that we delete those nodes?


  • 0
    E

    @asharboys Emm.. It's a good practice to do that. In real world we should take care of it, but in OJ, this is not that important in this case. Just keep delete in mind and it's OK.


  • 0
    Z

    @asharboys You are right. In real interview, you should mention that it is necessary to free memory, but you don't need actually do it due to limited time.


  • 1

    @asharboys I totally agree with you. You need to use delete in the interview. But here in the competition, it is okay to get to the top of the leaderboard. This is wrong, but can be ignored as collateral damage. :)


  • 0

    @zestypanda Nice solution. Would you please mind explaining? I more-or-less got the approach, but it would be helpful if you could explain it once. Thank you in anticipation.


  • 0
    Z

    @BatCode Could you share a code to free the memory? I have just wrote one, but it failed the online judge. It seems that if I delete the pointer, the judge code deletes it again, which is an error. Thank you!


  • 0

    @zestypanda I was requesting you to explain your original approach (without that delete operation). I couldn't code this up; else I would have shared for sure. Sorry...


  • 0
    A

    @Eagleming @zestypanda and @BatCoder : Thanks for clarifying, appreciate your help!


  • 0

    @zestypanda

    else if the root value < L
          because of binary search tree property, the root and the right subtree are not in range;
          we need return trimmed left subtree.
    

    I think you reversed the conditions while explaining.. As I understand, what you do in the code (is correct and) different.


  • 0
    Z

    @BatCoder LOL. Thanks for pointing out! Fixed.


  • 0

    @zestypanda Thank you. I appreciate your help! :)


  • 4

    @zestypanda said in C++, recursion:

    @BatCode Could you share a code to free the memory? I have just wrote one, but it failed the online judge. It seems that if I delete the pointer, the judge code deletes it again, which is an error. Thank you!

    I had the same experience, also getting an error. But it worked once I avoided deleting the root of the whole tree. This solution gets accepted:

    TreeNode* trimBST(TreeNode* root, int L, int R, bool top=true) {
        if (!root)
            return root;
        root->left = trimBST(root->left, L, R, false);
        root->right = trimBST(root->right, L, R, false);
        if (root->val >= L && root->val <= R)
            return root;
        auto result = root->val < L ? root->right : root->left;
        if (!top)
            delete root;
        return result;
    }
    

    I think it's a bug in the judge. In general we should definitely delete[*]. We're the ones removing nodes from the tree, so we're the ones in the position to "delete" and thus responsible for doing so. And the whole tree's root is no different from any other node, there shouldn't be a distinction.

    [*] Though in a contest I wouldn't, as it takes time and - as this experience shows - can cause trouble.


  • 0
    Z

    @StefanPochmann Thank you for the clarification and the "trick"!


Log in to reply
 

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