Iterative method to delete nodes


  • 0
    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return root;
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null && cur.val != key) {
                parent = cur;
                if (key > cur.val) cur = cur.right;
                else cur = cur.left;
            }
            if (cur == null) return root;
            if (cur.left == null) {
                if (parent == null) return root.right;
                if (parent.left == cur) parent.left = cur.right;
                else parent.right = cur.right;
                return root;
            } else {
                TreeNode p2 = cur.left;
                TreeNode p2Parent = cur;
                while (p2.right != null) {
                    p2Parent = p2;
                    p2 = p2.right;
                }
                // Replace cur node with p2
                // If p2 is child of cur
                if (cur == p2Parent) {
                    p2.right = cur.right;
                    if (parent == null) return p2;
                    if (parent.left == cur) parent.left = p2;
                    else parent.right = p2;
                    return root;
                }
                else {
                    p2Parent.right = p2.left;
                    p2.left = cur.left;
                    p2.right = cur.right;
                    if (parent == null) return p2;
                    if (parent.left == cur) parent.left = p2;
                    else parent.right = p2;
                    return root;
                }
            }
        }
    }
    

Log in to reply
 

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