Very Concise C++ Solution for General Binary Tree not only BST


  • 20
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if (!root) return nullptr;
            if (root->val == key) {
                if (!root->right) {
                    TreeNode* left = root->left;
                    delete root;
                    return left;
                }
                else {
                    TreeNode* right = root->right;
                    while (right->left)
                        right = right->left;
                    swap(root->val, right->val);    
                }
            }
            root->left = deleteNode(root->left, key);
            root->right = deleteNode(root->right, key);
            return root;
        }
    };
    

  • 0
    A

    Nice job for lazy deletion.


  • 0
    W

    helpful,thanks


  • 1
    B

    @amosbird This is not lazy deletion. Node is deleted. This is a O(n) solution, but general for binary trees.


  • 0
    A

    @buylv-gucci It is in the sense of swapping instead of deleting directly.


  • 0

    @amosbird
    If you understand my code clearly, you will find it will be deleted later after swap.


  • 0
    A

    @zyoppy008 isn't that laziness :-P


  • 0

    @amosbird
    You are right.


  • 0

    @zyoppy008 Nice concise solution.

    For the recursion on left subtree deleteNode(root->left, key), would it be OK to do it only if else if (root->val > key)? It seems that the left subtree can be left alone if the key to search is no less than root. I am not sure if this will impact your node deletion.


  • 1
    C

    How do you come up with this solution? Do you recommend any textbook?Thansk


  • 4
    C

    My two cents
    This is a great algorithm that can beats more than more than 50% of the solutions.
    But the time complexity is actually O(n) instead of O(lgN) which is requested by the problem.

    The following changes make it O(lgN) while somehow lower the performance , :(

    TreeNode* deleteNode(TreeNode* root, int key) {
        if( !root )
            return nullptr;
        
        if( root->val == key ){
            if( !root->right )
                return root->left;
            else{
                TreeNode* n = root->right;
                while( n->left )
                    n = n->left;
                swap( n->val , root->val );
                
                root->right = deleteNode( root->right , key );
                return root;
            }
        }
        
        if( root->val > key )
            root->left = deleteNode( root->left , key );
        if( root->val < key )
            root->right = deleteNode( root->right , key );
        return root;
    }

  • 0
    K

    We shuold delete the node with the key value. But in this case,we just delete one node equall to key.If the root of the subtree is equall to key,we do nothing.


  • 1
    M

    @caojiayin1985 is there memory leak since you did not actually "delete" the node from the heap by just return root->left?


  • 0
    L

    @zyoppy008 said in Very Concise C++ Solution for General Binary Tree not only BST:

    If you understand my code clearly, you will find it will be deleted later after swap.
    you delete the node after all , but travel the swap node branch repeatedly, and the code not concisely.


  • 0
    Q

    @MapleLeaf2012 It's not memory leak nor lazy deletion. If the node we found has no right children, the node will be deleted right away. If the node has right children, the node will be swapped with the left-most leaf node of the right subtree. After swapping, the key has become a left leaf node and will be deleted during next loop.


Log in to reply
 

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