Iterative solution in Java, O(h) time and O(1) space


  • 28
    E
        private TreeNode deleteRootNode(TreeNode root) {
            if (root == null) {
                return null;
            }
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode next = root.right;
            TreeNode pre = null;
            for(; next.left != null; pre = next, next = next.left);
            next.left = root.left;
            if(root.right != next) {
                pre.left = next.right;
                next.right = root.right;
            }
            return next;
        }
        
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode cur = root;
            TreeNode pre = null;
            while(cur != null && cur.val != key) {
                pre = cur;
                if (key < cur.val) {
                    cur = cur.left;
                } else if (key > cur.val) {
                    cur = cur.right;
                }
            }
            if (pre == null) {
                return deleteRootNode(cur);
            }
            if (pre.left == cur) {
                pre.left = deleteRootNode(cur);
            } else {
                pre.right = deleteRootNode(cur);
            }
            return root;
        }
    

    Find the node to be removed and its parent using binary search, and then use deleteRootNode to delete the root node of the subtree and return the new root node. This idea is taken from https://discuss.leetcode.com/topic/67309/an-easy-understanding-o-h-time-o-1-space-java-solution.

    I'd also like to share my thinkings of the other solutions I've seen.

    1. There are many solutions that got high votes using recursive approach, including the ones from the Princeton's Algorithm and Data Structure book. Don't you notice that recursive approach always takes extra space? Why not consider the iterative approach first?
    2. Some solutions swap the values instead of swapping the nodes. In reality, the value of a node could be more complicated than just a single integer, so copying the contents might take much more time than just copying the reference.
    3. As for the case when both children of the node to be deleted are not null, I transplant the successor to replace the node to be deleted, which is a bit harder to implement than just transplant the left subtree of the node to the left child of its successor. The former way is used in many text books too. Why? My guess is that transplanting the successor can keep the height of the tree almost unchanged, while transplanting the whole left subtree could increase the height and thus making the tree more unbalanced.

  • 0
    C

    nice solution.
    and C++ version:

    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(root == NULL) return root;
            TreeNode *cur = root, *pre = NULL;
            while(cur != NULL && cur->val != key){
                pre = cur;
                if(key > cur->val){
                    cur = cur->right;
                }else{
                    cur = cur->left;
                }
            }
            if(pre == NULL) return deleteRootNode(cur);
            else if(pre->left == cur){
                pre->left = deleteRootNode(cur);
            }else{
                pre->right = deleteRootNode(cur);
            }
            return root;
        }
        
        TreeNode* deleteRootNode(TreeNode* root) {
            if (root == NULL) {
                return NULL;
            }
            if (root->left == NULL) {
                return root->right;
            }
            if (root->right == NULL) {
                return root->left;
            }
            TreeNode *next = root->right, *pre = NULL;
            while(next->left != NULL){
                pre = next;
                next = next->left;
            }
            if(pre == NULL) root->right = next->right;
            else pre->left = next->right;
            root->val = next->val;
            return root;
        }
    };
    

  • 0
    K

    Hey Eaglesky,
    Strongly agree with your 3rd thought.

    As for the case when both children of the node to be deleted are not null, I transplant the successor to replace the node to be deleted, which is a bit harder to implement than just transplant the left subtree of the node to the left child of its successor. The former way is used in many text books too. Why? My guess is that transplanting the successor can keep the height of the tree almost unchanged, while transplanting the whole left subtree could increase the height and thus making the tree more unbalanced.


  • 0
    H

    While the recursive solutions are simpler to implement, this solution should do better on performance. Even simple recursive calls that don't branch out have a memory overhead.
    And his third point about keeping the trees balanced is a very interesting one.

    Great answer!


  • 0
    A

    You, sir/lady, have given a very fine analysis of all the approaches. I would agree with your conclusion. Only 1.3% of submissions in java could beat this.


  • 1

    @eaglesky I've got both iterative and recursive for comparison here. While you are correct that the recursive stack will take O(h) memory it's not a lot, O(h) is pretty small. Consider a million nodes for balanced tree this height is only about 20, pretty small. In any case you're not going to notice that kind of difference from OJ timer. I didn't, I ran both solutions a few times, as usual results varied a lot and neither was the clear winner.

    Also I'd argue that the tree will be no more balanced using your node combining scheme than the other. To keep a balanced tree you'd need to use a balancing pass after each delete and insert. Correct me if I'm wrong here.

    As you can see the recursive is a bit simpler to code and a few less lines.

        public TreeNode DeleteNode(TreeNode root, int key) 
        {
            //return DeleteNode_Recursive(root, key);
            return DeleteNode_Iterative(root, key); 
        }
        
        public TreeNode DeleteNode_Recursive(TreeNode root, int key) 
        {
            if (root == null) return root;
            if (root.val == key) return Combine(root.left, root.right);
            if (key < root.val) root.left = DeleteNode(root.left, key);
            else root.right = DeleteNode(root.right, key);
            return root;
        }
        
        public TreeNode DeleteNode_Iterative(TreeNode root, int key) 
        {
            TreeNode node = root;
            TreeNode parent = null;
            
            while (node != null && node.val != key)
            {
                parent = node;
                if (key < node.val) node = node.left;
                else node = node.right;
            }
            if (node == null) return root; // not found
            
            TreeNode replacement = Combine(node.left, node.right);
            
            // replace root
            if (parent == null) return replacement;
            
            // replace node within tree
            if (node == parent.left) parent.left = replacement;
            if (node == parent.right) parent.right = replacement; 
            return root;
        }
        
        public TreeNode Combine(TreeNode left, TreeNode right)
        {
            if (left == null) return right;
            if (right == null) return left;
            TreeNode node = right;
            while (node.left != null)
            {
                node = node.left;
            }
            node.left = left;
            return right;
        }
    

  • 1
    E

    @jdrogin For balanced tree, the difference is indeed small. However the question itself doesn't assume the tree is balanced, does it? In the worst case, h could be equal to the number of nodes, which is a huge number if there are millions of nodes, and a recursive solution could result in "stack overflow" in such cases. The OJ probably does not have many extreme cases for unbalanced trees, and it does not need to since it is just a tool for practicing coding. So it does not make sense to make conclusions based on the test result of OJ. The iterative solution I posted is O(1) space, and the recursive solution is O(h), that is the fact, and though h is small on OJ, it could be very large in real-world applications.

    You are right about saying "To keep a balanced tree you'd need to use a balancing pass after each delete and insert". And actually I didn't say the node combining scheme can strictly keep the tree balanced. Based on my observation, this way can keep the height of the tree almost unchanged, and I think this is right for most of the trees, but there might be a few exceptions. But anyway, that's just my guess, and I can't prove it.


  • 0
    G

    @eaglesky
    My iterative solution..

    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
    Y
    public class Solution {
        private TreeNode deleteNode(TreeNode root){
            if(root==null) return root;
            if(root.left!=null && root.right!=null){
                    TreeNode cur = root.left;
                    while(cur.right!=null) cur = cur.right;
                    cur.right = root.right;
                    return root.left;
            }else{
                return root.left==null?root.right:root.left;
            }
        }
        public TreeNode deleteNode(TreeNode root, int key){
            if(root==null) return root;
            TreeNode toDelete = root, parent = null;
            while(toDelete!=null){
                if(toDelete.val==key) break;
                else{
                    parent = toDelete;
                    if(toDelete.val<key) toDelete = toDelete.right;
                    else toDelete = toDelete.left;
                }
            }
            if(toDelete==null) return root;//the node unfound
            if(parent==null) return deleteNode(root);
            else if(parent.left == toDelete) parent.left = deleteNode(toDelete);
            else parent.right = deleteNode(toDelete);
            return root;
        }
    }
    

    the difference between the two methods is:
    OP's method promote the smallest value from right tree(or biggest value from left tree) to root while the less coded version here does not do that

    I would say OP's method better because after deletion, the tree has a higher probability to keep being balanced than the less coded version


  • 0
    Z

    @eaglesky Great solution! Totally agree with point 3. Transplanting the whole left subtree will increase the height, POTENTIAL to O(n) height in the worst case.


Log in to reply
 

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