Easy iterative java solution with comments


  • 0
    D
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            
            //Base case: if root is null, or key is not found, return root
            if(root==null)
                return root;
            
            //General case: to keep track of node where key is found and its parent
            TreeNode prev=null;
            TreeNode current=root;
            boolean keyFound=false;
            
            /*Check to see if key is present in tree,
            if present, set keyFound to true an exit,
            else based on key value recurse on left or right subtree */
            while(current!=null)
            {
                if(current.val==key)
                {
                    keyFound=true;
                    break;
                }
                
                prev=current;
                
                if(key<current.val)
                    current=current.left;
                else
                    current=current.right;
            }
            
            //if key is found
            if(keyFound)
            {
                
                //Case 1: if key node is the root
                if(current==root)
                {
                    
                    //if either subtree is null, return the other subtree as the root node
                    if(current.left==null)
                        return current.right;
                    
                    if(current.right==null)
                        return current.left;
                    
                    //if both subtrees are present, set right subtree as root and attach left subtree as left child of right subtree
                    TreeNode newRoot=current.right;
                    
                    TreeNode iter=newRoot;
                    
                    while(iter.left!=null)
                    {
                         iter=iter.left;
                    }
                    
                    iter.left=current.left;
                    
                    //set the newRoot as root node
                    root=newRoot;
                }
                
                
                //Case 2: if key node is an internal node
                else
                {
                    //Case 3a: if key node is left subtree of its parent
                    if(prev.left==current)
                    {
                        
                        //if either subtree of key node is null, set other subtree as left child of parent node
                        if(current.left==null)
                            prev.left=current.right;
                        
                        else if(current.right==null)
                            prev.left=current.left;
                        
                        /*if both subtrees are present,set left subtree of keynode as left child of parent node
                        set right subtree of key node as right child of left subtree of key node */
                        else
                        {
                            TreeNode iter=current.left;
                            
                            while(iter.right!=null)
                            {
                                iter=iter.right;
                                
                            }
                            
                            iter.right=current.right;
                            prev.left=current.left;
                        }
                    }
                    
                    //Case 3b: if key node is right subtree of its parent
                    else if(prev.right==current)
                    {
                        //if either subtree of key node is null, set other subtree as left child of parent node
                        if(current.left==null)
                            prev.right=current.right;
                        
                        else if(current.right==null)
                            prev.right=current.left;
                        /*if both subtrees are present,set right subtree of keynode as right child of parent node
                        set left subtree of key node as left child of right subtree of key node */
                        else
                        {
                            TreeNode iter=current.right;
                            
                            while(iter.left!=null)
                                iter=iter.left;
                            
                            iter.left=current.left;
                            prev.right=current.right;
                        }
                    }
                }
            }
            
            //return root
            return root;
            
        }
    }
    

Log in to reply
 

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