Recursive Java code with explanation


  • 0
    L
       public TreeNode deleteNode(TreeNode root, int key) {
            if(root==null || (root.val==key && root.left==null && root.right==null)) {
                //root node is a leaf node.
                return null;
            }
            helper(root,null,false,key);
            return root;
        }
        
        private void helper(TreeNode root, TreeNode parent, boolean isleft, int key) {
            if(root==null) {
                return;
            }
            
            if(key==root.val) {
                //3 scenarios: 1. leaf, 2. one child, 3. two children.
                //case 1: leaf node.
                if(root.left==null && root.right==null) {
                  if(isleft) {
                      parent.left=null;
                  }            
                  else {
                      parent.right=null;
                  }
                }
                //case 2: one child.
                else if(root.left==null || root.right==null) {
                    if(parent==null) {
                        //dealing with the root.
                        TreeNode left = null;
                        TreeNode right = null;
                        if(root.left!=null) {
                            root.val = root.left.val;
                            left = root.left.left;
                            right = root.left.right;
                            root.left = left;
                            root.right = right;
                        }
                        else {
                            root.val = root.right.val;
                            left = root.right.left;
                            right = root.right.right;
                            root.left = left;
                            root.right = right;
                        }
                        return;
                    }
                    if(isleft) {
                        parent.left = root.left!=null?root.left:root.right;
                    }
                    else {
                        parent.right = root.right!=null?root.right:root.left;
                    }
                }
                else {
                    //case 3://both children.
                    //go to the right child and find leftmost children.
                    TreeNode p = root.right;
                    TreeNode node = p.left;
                    if(node==null) {
                        //no left node.
                        root.val = p.val;
                        root.right = p.right;
                        p.right = null;
                        return;
                    }
                    while(node.left!=null) {
                        p = node;
                        node = node.left;
                    }
                    root.val = node.val;
                    p.left = node.right;
                }
            }
            
           if(key<root.val) {
            //go left.
            helper(root.left,root,true,key);
           }
           else {
            //go right.
            helper(root.right,root,false,key);
           }
        }
    }
    

Log in to reply
 

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