Recursive Easy to Understand Java Solution


  • 114
    B

    Steps:

    1. Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree
    2. Once the node is found, have to handle the below 4 cases
    • node doesn't have left or right - return null
    • node only has left subtree- return the left subtree
    • node only has right subtree- return the right subtree
    • node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(key < root.val){
            root.left = deleteNode(root.left, key);
        }else if(key > root.val){
            root.right = deleteNode(root.right, key);
        }else{
            if(root.left == null){
                return root.right;
            }else if(root.right == null){
                return root.left;
            }
            
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    
    private TreeNode findMin(TreeNode node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
    

  • 1
    C

    I think you also need to return null if both root.left and root.right is null


  • 2
    B

    @crrapran if root.left and root.right are null, it will fall into the

    if(root.left == null){
        return root.right;
    

    and return null


  • 1
    K

    Thank you for your concise solution @booboohsu ! I'm asking myself what's your inspiration for such good recursion. Do you think practising functional programming would help?


  • 1
    C

    @booboohsu This line is so cool.

    root.right = deleteNode(root.right, root.val);


  • 2
    R

    Thank you for your solution, it is great, I reformat it a little bit.

    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return null;
            if (key < root.val) root.left = deleteNode(root.left, key);
            else if (key > root.val) root.right = deleteNode(root.right, key);
            else if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                root.val = findMin(root.right);
                root.right = deleteNode(root.right, root.val);
            }
            return root;
        }
        private int findMin(TreeNode node) {
            while (node.left != null) node = node.left;
            return node.val;
        }
    }
    

  • 0

    @booboohsu
    i think there is a typo, it should be
    "only has left subtree, return left subtree"
    "only has right subtree, return right subtree"


  • 0
    B

    @Lara yep you are correct. Thanks for catching that. I have updated it.


  • 28

    I have a slightly different version, while handling in the event of node being found, instead of calling recursion again I handle it right away, this makes my running time faster

     public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return null;
            
            if (root.val > key) {
                root.left = deleteNode(root.left, key);
            } else if (root.val < key) {
                root.right = deleteNode(root.right, key);
            } else {
                if (root.left == null) return root.right;
                if (root.right == null) return root.left;
                
                TreeNode rightSmallest = root.right;
                while (rightSmallest.left != null) rightSmallest = rightSmallest.left;
                rightSmallest.left = root.left;
                return root.right;
            }
            return root;
        }
    

  • 1
    O

    @booboohsu
    Cool solution.

    @meowmeow
    Awesome idea!

    I was thinking, instead of recursing again, when you find the rightSmallest, can you set to null (i.e parentOfRightSmallest.left = rightSmallest.right;).

    If you do it that way, the tree's height would be the same or -1 as the old tree, versus in your solution the height could be as big as the double of the original.


  • 0
    R

    Hi, I am new to this and need some help. I keep getting error "Memory Limit Exceeded". Need some insights on how can I improve my solution. I know the recursive solution works (I tried), but just curious on mine as well. Thanks!

    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            //keep track of node to be deleted
    		//its parent node
    		//and whether the node to be deleted is left or right child of its parent isLeftChild
    		TreeNode current = root;
    		TreeNode parent = root; //initialize parent as root
    		boolean isLeftChild = false;
            
            //find if node to be deleted exists
            while(current != null && current.val != key) {
                parent = current;
                if (key < current.val) {
                    current = current.left;
                    isLeftChild = true;
                } else {
                    current = current.right;
                    isLeftChild = false;
                }
            }
            
            //check if node to be deleted exists - 
            if (current == null) return root;
            
            //case 1 - current has no left and right childs
            if (current.left == null && current.right == null) {
                if (current == root) {
                    root = null;
                    //return root;
                } else {
                    if (isLeftChild) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }
            }
            //case 2.1 - node has one child - left
            else if (current.right == null) {
                if (current == root) {
                    root = current.left;
                } else if (isLeftChild) {
                    parent.left = current.left;
                } else {
                    parent.right = current.left;
                }
            }
            //case 2.2 - has only one child - right
            else if (current.left == null) {
                if (current == root) {
                    root = current.right;
                } else if (isLeftChild) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
            //case 3 - node has both left and right subtree
            //in this case get inorder successor - lefmostchild of the right subtree
            else {
                if (current == root) {
                    root = leftMostChild(current.right);
                    if (current.right != null) {
                        root.right = current.right;    
                    }
                    
                } else if (isLeftChild) {
                    parent.left = leftMostChild(current.right);
                    if (current.left != null) {
                        parent.left.left = current.left;
                    }
                } else {
                    parent.right = leftMostChild(current.left);
                    if (current.right != null) {
                        parent.right.right = current.right;    
                    }
                    
                }
            }
            
            return root;
        }
        
        public static TreeNode leftMostChild(TreeNode n) {
            if (n == null) return null;
            while (n.left != null) {
                n = n.left;
            }
            return n;
        }
        
    }
    

  • 0
    Y

    Hey Just wondering what could be time and space complexity of this. It seems to be O(h) time complexity and space ??


  • 0
    Q

    @rajatsharma19
    I modified part of your codes. Now it's accepted.

            //case 3 - node has both left and right subtree
            //in this case get inorder successor - lefmostchild of the right subtree
            else {
                TreeNode node = leftMostChild(current.right);
                int val = node.val;
                root = deleteNode(root, val);
                current.val = val;
            }
    

  • 2
    G

    @booboohsu : Great solution. I extended it a little to actually free the memory for the node that needs to be deleted.

        TreeNode* deleteNode(TreeNode* root, int key) {
            if (root) {
                if (root->val < key) root->right = deleteNode(root->right, key);
                else if (root->val > key) root->left = deleteNode(root->left, key);
                else {
                    if (root->left && root->right) {
                        int min = getMin(root->right);
                        root->val = min;
                        root->right = deleteNode(root->right, min);
                    } else {
                        TreeNode* to_delete = root;
                        if (root->left) root = root->left;
                        else if (root->right) root = root->right;
                        else root = NULL;
                        delete to_delete;
                    }
                }
            }
            return root;
        }
        int getMin(TreeNode* root) {
            while (root->left) root = root->left;
            return root->val;
        }
    

  • 0
    B

    What is the time complexity? Is the worst case O(n^2)?


  • 0
    G

    @Bigbear1991 Runtime complexity is O(h) where h is the height of the tree. I think we will hit the worse case in two scenarios:

    1. Deleting a leaf.
    2. Deleting any node on a full BST.

  • 0
    O

    @Bigbear1991 the first solution above likely runs O(h) where h is the height as the worst case, that occurs when deleting a root node of a large tree.

    See:
    '''
    TreeNode minNode = findMin(root.right);
    '''

    That line causes every node along the path to be visited best case once (delete leaf), worst case twice (delete root).

    Potential improvement is to restart the search from the parent of the min node. In that case you would traverse the tree along its height once and only once, therefore while the time complexity still is O(h), you would traverse the tree once at worst. Or use BST properties to reconfigure the tree when you have found the replacement node for the root, in delete root case. That keeps worst case O(h) but allows a chance to early exit the loops and makes average case faster. See @meowmeow post above for the code.


  • 0
    B

    @meowmeow said in Recursive Easy to Understand Java Solution:

    I have a slightly different version, while handling in the event of node being found, instead of calling recursion again I handle it right away, this makes my running time faster

                TreeNode rightSmallest = root.right;
                while (rightSmallest.left != null) rightSmallest = rightSmallest.left;
                rightSmallest.left = root.left;
                return root.right;
            }
            return root;
        }
    

    could you explain this particular part? I understand you find the min node, but what is the

    rightSmallest.left = root.left;
    return root.right;
    

    do?


  • 0

    I process the smallest left node right after finding it instead of doing another recursion

    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if(root == null) return root;
    
            if(root.val < key){
                root.right = deleteNode(root.right, key);
            }else if(root.val > key){
                root.left = deleteNode(root.left, key);
            }else{
                //root.val == key
                if(root.left == null){
                    return root.right;
                }else if(root.right == null){
                    return root.left;
                }else if(root.right.left == null){
                    root.right.left = root.left;
                    return root.right;
                }else{
                    TreeNode min = findMin(root.right);
                    min.left = root.left;
                    min.right = root.right;
                    return min;
                }
            }
    
            return root;
        }
    
        private TreeNode findMin(TreeNode root){
            while(root.left.left != null){
                root = root.left;
            }
            TreeNode min = root.left;
            //easy to forget this step
            root.left = min.right;
            return min;
        }
    }
    

  • 0

    I did not come up with the smart idea of editing node value instead of reconnecting node, so here is my code for node reconnecting way. It shares similar time performance as the recursive way.

     public TreeNode deleteNode(TreeNode root, int key) {
            if(root == null) return root;
            if(root.val < key) root.right = deleteNode(root.right, key);
            else if(root.val > key) root.left = deleteNode(root.left, key);
            else{
                if(root.left == null) return root.right;
                else if(root.right == null) return root.left;
                else{
                    TreeNode newRoot = root.right, par = null;
                    while(newRoot.left != null){
                        par = newRoot;
                        newRoot = newRoot.left;
                    }
                    if(par == null){
                        newRoot.left = root.left;
                        return newRoot;
                    }
                    par.left = newRoot.right;
                    newRoot.left = root.left;
                    newRoot.right = root.right;
                    return newRoot;
                }
            }
            return root;
        }
    

    alt text


Log in to reply
 

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