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;
        }
    }
    

  • 0
    F

    My iterative solution. The idea is simple: First check whether the given root is the node we want to delete. If so, use helper function to return new root. Else, use binary search to find the node we want to delete, once we find it, call helper function to delete it and return new node.

    The idea of helper function is assumed the given node is the node we want to delete. So we check if its left child is null, if so we can return right child directly. Vice versa. But if both child not null, we will find the largest node of left subtree, then set right child of given node to be the right child of this largest node of left subtree, then return left child of given node.

    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            if (root.val == key) {
                return helper(root);
            }
            TreeNode dummy = root;
            while (root != null) {
                if (root.val > key) {
                    if (root.left != null && root.left.val == key) {
                        root.left = helper(root.left);
                        break;
                    } else {
                        root = root.left;
                    }
                } else {
                    if (root.right != null && root.right.val == key) {
                        root.right = helper(root.right);
                        break;
                    } else {
                        root = root.right;
                    }
                }
            }
            return dummy;
        }
        public TreeNode helper(TreeNode root) {
            if (root.left == null) {
                    return root.right;
                } else if (root.right == null){
                    return root.left;
                } else {
                    TreeNode rightChild = root.right;
                    TreeNode lastRight = findLastRight(root.left);
                    lastRight.right = rightChild;
                    return root.left;
                }
        }
        public TreeNode findLastRight(TreeNode root) {
            if (root.right == null) {
                return root;
            }
            return findLastRight(root.right);
        }
    }
    

Log in to reply
 

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