Simple recursive solution | C++ | 46ms


  • 0
    P

    The code below does the following:

    • Recursively calls itself till the node to be deleted is found. Leverage BST property to traverse the tree. Recursive is required since we might need to update pointers along the way.
    • When the node to be deleted is found, find the smallest element in the right sub-tree (call it 'next'), move its value to current node and delete 'next'.
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if     (root == nullptr)  return root;
            else if(key < root->val)  root->left  = deleteNode(root->left,  key);
            else if(key > root->val)  root->right = deleteNode(root->right, key);
            /* Cur node has to be deleted, handle 3 cases below */
            else {
                auto oldroot = root;
                if     (root->left  == nullptr)  root = root->right;
                else if(root->right == nullptr)  root = root->left;
                /* Find smallest in right sub-tree, copy its val and delete it */
                else {
                    auto next   = getMinNode(root->right);
                    root->val   = next->val; /* curval = smallest in right subtree */
                    root->right = deleteNode(root->right, next->val);
                    /* next will already be deleted, nothing to del in this case */
                    oldroot     = nullptr;
                }
                delete oldroot;
            }
            return root;
        }
    private:
        /* Find the left-most node in the tree     */
        inline TreeNode* getMinNode(TreeNode* x) {
            for(; x != nullptr && x->left != nullptr; x = x->left);
            return x;
        }
    };
    

Log in to reply
 

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