Yet another C++ soln without memory leak O(h) time.


  • 0
    B

    I see a lot of C++ solutions with memory leaks.
    Here is a soln that does the following:

    • uses recursion to find the node with key as its val.
    • If key if found in a node without a right subtree, then we store the left subtree over as replacement.
    • If key is found in a node with a valid right subtree, we use a two pointer strategy to find min, and later swap and delete the node with key val.
    TreeNode* deleteNode(TreeNode* root, int key) {
            if (!root)
                return root;
            
            if (root->val == key) {
                if (!root->right) {
                    TreeNode* left = root->left;
                    delete root;
                    return left;
                } else {
                    //find the min in the right tree, swap and bubble out
                    TreeNode* minNode = root->right;
                    TreeNode* prevMinNode = nullptr;
                    
                    while(minNode->left) {
                        prevMinNode = minNode;
                        minNode = minNode->left;
                    }
                    
                    swap(minNode->val, root->val);
                    
                    if (prevMinNode)
                        prevMinNode->left = minNode->right;
                    else 
                        root->right = minNode->right;
                    delete minNode;
                    
                    return root;
                }
                
            } else if (key < root->val)
                root->left = deleteNode(root->left, key);
            else
                root->right = deleteNode(root->right, key);
            
            return root;
        }
    

Log in to reply
 

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