C++ recursive. Algorithm from Geeks For Geeks.


  • 0
    P
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            return rec(root, key);
        }
        TreeNode* rec(TreeNode *root, int key)
        {
            if(!root)return nullptr; \\standard guard
            if(root -> val < key) root -> right = rec(root -> right, key); \\search right
            if(root -> val > key) root -> left = rec(root -> left, key); \\search left.
            if(root -> val == key) \\ when found we check all cases. if left, if right, if both, if none.
            {
                if(!root -> left && !root -> right) return NULL;
                if(!root -> left) return  root -> right;
                if(!root -> right)return  root -> left;
                if(root -> left && root -> right) \\ when both exist, we cannot simply delete. we need to move the lowest value at the right tree to the current position as it is the only one that will satisfy.
                {
                    auto* mnvl = [](TreeNode* root) -> TreeNode* {while(root -> left) root = root -> left; return root;}(root -> right); \\simple left traversal to find the lowest val.
                    root -> val = mnvl -> val;
                    root -> right = rec(root -> right, mnvl -> val) ; \\ since the mininmum value is not at the root, we need to delete this min value. It happens in O(h).
                    return root;
                }
            }
            return root;
        }
    };

Log in to reply
 

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