Very Concise Recursive C++ Solution

  • 0

    We will only do deletion when root->val == NULL, so if root->val > key we can know that the key is in the left subtree, then root->left = deleteNode(root->left, key), if root->val < key should do root->right = deleteNode(root->right, key).

    When root->val == NULL we need to delete root. If root->left == NULL && root->right == NULL we can just delete root and return NULL, else we can chose root->left or root->right to be the new root in case it is not NULL.

    class Solution 
        TreeNode* deleteNode(TreeNode* root, int key) 
        	if(root == NULL) return NULL;
            if(root->val == key)
            		TreeNode* p = root->right;
            		while(p->left) p = p->left;
            		p->left = root->left;
            		return root->right;
            	else if(root->left)
            		return root->left;
            	else return NULL;
            if(root->val > key)
            	root->left = deleteNode(root->left, key);
            if(root->val < key)
            	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.