450. Delete Node in a BST 2019 practice

Here is the link.


It is my practice in 2019. I have to work on so many algorithms, one thing I can do is to share more content on this practice, and also work on my patience. One thing I can do is to go over example tree, and work on the example more carefully, so that next time I will not miss an edge case.

To be a good engineer, I have to learn how to work on the example tree, go over the tree at least once to show myself how to approach the problem. I am not afraid to implement any idea I may come out; only thing I have to work on is to pay attention to edge case, do not rely on online judge to remind me my mistakes.

Here is the copy of content in Leetcode discuss. 

It is one of mock interview algorithms. I spent first 10 minutes to draw a tree and then figure out the solution by myself.

To be a good problem solver, I have to work on my patience and draw some example tree, and work on the edge case carefully. Here is the tree I like to present and I explain how to solve the problem in multiple steps.

Given root node with value 6, and key 4, I need to find the node with value 4, and then search it's left subtree to find maximum value node first.

Given root node with value 6, and key 4, I worked on the above tree, go to node 4 left subtree and try to find maximum value in left subtree. I find node 3 and it's parent node, and then node 4's value will be updated to 3, and node 3's parent will have right child set as node's left child.

I ran the code against online judge, and then I found out that I missed another case. What if the node 4's left child is largest node in left subtree.

I need more patience and think about more carefully in order to solve the problem in shortest time.

Here are hightlights of my solution:

1. Since the root node can be the node with key value, and the tree maybe is the one with one node. So I create a dummy node and make root node as its left child;
2. Use binary search to search key value in binary search tree, either root node has the value key, or go to left or right to search the node;
3. Use step 2 to find node with key value first, and work on the case if node with key value has left child;
4. Write a while loop to find rightmost node in left subtree, and also keep parent node;
5. Set key value node with rightmost node's value
6. reconnect rightmost node's parent node's right child, remove rightmost node from the tree
7. Work on the right subtree case
8. Find out that I missed the edge case - step 4, left child of node value 4 is the largest node in left subtree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /// <summary>
        /// binary search the node
        /// binary search tree
        /// </summary>
        /// <param name="root"></param>
        /// <param name="key"></param>
        /// <returns></returns>
        public TreeNode DeleteNode(TreeNode root, int key)
        {
            if (root == null)
                return root;

            TreeNode parentNode = new TreeNode(1);
            parentNode.left = root; 
             
            traverseTree(root, parentNode, true, key);

            return parentNode.left; 
        }

        /// <summary>
        /// May 30, 2019
        /// </summary>
        /// <param name="root"></param>
        /// <param name="parentNode"></param>
        /// <param name="isLeft"></param>
        /// <param name="key"></param>
        private static void traverseTree(TreeNode root, TreeNode parentNode, bool isLeft, int key)
        {
            if (root == null)
                return;

            var value = root.val;
            if (value == key)
            {
                if (root.left == root.right)
                {
                    if (isLeft)
                        parentNode.left = null;
                    else
                        parentNode.right = null;

                    return;
                }

                //Find left
                if (root.left != null)
                {
                    // find rightmost node, which should not have right child
                    // make its parent node's right child to it's left child
                    var largestNode = root.left;
                    var parent = parentNode; 
                    while (largestNode.right != null)
                    {
                        parent = largestNode;
                        largestNode = largestNode.right;                        
                    }

                    var largestValue = largestNode.val;
                    root.val = largestValue;

                    if (largestNode != root.left)
                    {
                        parent.right = largestNode.left;                       
                    }
                    else 
                    {
                        root.left = largestNode.left;                       
                    }

                    largestNode = null; // set null
                }
                else if (root.right != null)
                {
                    // find leftmost node, which should not have left child
                    // make its parent node's left child to it's right child
                    var smallestNode = root.right;
                    var parent = parentNode;
                    while (smallestNode.left != null)
                    {
                        parent = smallestNode;
                        smallestNode = smallestNode.left;
                    }

                    var smallestValue = smallestNode.val;
                    root.val = smallestValue;

                    if (smallestNode != root.right)
                    {
                        parent.left = smallestNode.right;
                    }
                    else
                    {
                        root.right = smallestNode.right;
                    }

                    smallestNode = null; // set null 
                }

                return;
            }

            if (value < key)
            {
                traverseTree(root.right, root, false, key);
            }
            else
            {
                traverseTree(root.left, root, true, key);
            }
        }
}