Java Solution 0(h) iterative approach


  • 1
    C
    public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode prevNode = null, cur = root;
            boolean leftChild = false, nodeFound = false;
            
            while(cur != null){
                if(cur.val == key){
                    nodeFound = true;
                    break;
                }
                
                prevNode = cur;
                if(cur.val > key){
                    leftChild = true;
                    cur = cur.left;
                }
                else{
                    leftChild = false;
                    cur = cur.right;
                }
            }
            
            if(!nodeFound){
                return root;
            }
            
            if(prevNode == null){
                return deleteNode(cur);
            }
            
            if(leftChild){
                prevNode.left = deleteNode(cur);
            }
            else{
                prevNode.right = deleteNode(cur);
            }
            
            return root;
        }
        
        private TreeNode deleteNode(TreeNode node){
            if(node.left == null && node.right == null){
                return null;
            }
            
            if(node.left != null && node.right != null){
                TreeNode minRightSubtreeNode = findAndDeleteMinRightSubtree(node);
                node.val = minRightSubtreeNode.val;
            }
            else if(node.left != null){
                node = node.left;
            }
            else{
                node = node.right;
            }
            
            return node;
        }
        
        private TreeNode findAndDeleteMinRightSubtree(TreeNode node){
            TreeNode prevNode = node;
            node = node.right;
            boolean rightChild = node.left == null;
            
            while(node.left != null){
                prevNode = node;
                node = node.left;
            }
            
            if(rightChild){
                prevNode.right = node.right;
            }
            else{
                prevNode.left = node.right;
            }
            
            node.right = null;
            return node;
        }
    

  • 0
    G
    This post is deleted!

  • 0
    G

    @chiranjeeb2 I have similar approach

    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return root;
            TreeNode prev = null;
            TreeNode iter = root;
            if(root.val == key){ // special case of head
                return mergeLeft(root.left,root.right);
            }
            boolean isLeftChild = false;
            while(iter != null){
                if(iter.val == key) {
                    if (isLeftChild) {
                        prev.left = mergeLeft(iter.left,iter.right);
                    } else {
                        prev.right = mergeLeft(iter.left,iter.right);
                    }
                    return root;
                }
                prev = iter;
                if(iter.val > key){
                    iter = iter.left;
                    isLeftChild = true;
                } else {
                    iter = iter.right;
                    isLeftChild = false;
                }
            }
            return root;//not found case
        }
        
        public TreeNode mergeLeft(TreeNode leftNode, TreeNode rightNode){
            if(leftNode == null) return rightNode;
            if(rightNode == null) return leftNode;
            TreeNode iterator = rightNode;
            while(iterator.left!=null) {
                iterator = iterator.left;
            }
            iterator.left =leftNode;
            return rightNode;
        }
    }
    

Log in to reply
 

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