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;
}
};
Very Concise C++ Solution for General Binary Tree not only BST


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


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



@zyoppy008 Nice concise solution.
For the recursion on left subtree
deleteNode(root>left, key)
, would it be OK to do it only ifelse 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.

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

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

@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.

@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 leftmost leaf node of the right subtree. After swapping, the key has become a left leaf node and will be deleted during next loop.