Remove Node in Binary Search Tree

Remove Node in Binary Search Tree

25%

Accepted

Given a root of Binary Search Tree with unique value for each node.  Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Have you met this question in a real interview? 

Yes

Example

Given binary search tree:

          5

       /    \

    3          6

 /    \

2       4

Remove 3, you can either return:

          5

       /    \

    2          6

      \

         4

or :

          5

       /    \

    4          6

 /   

2

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        // write your code here
        TreeNode dummy = new TreeNode(-1);
        dummy.right = root;
        TreeNode cur = root;
        TreeNode pre = dummy;
        while(cur != null){
            if(cur.val == value){
                if(pre.right == cur){
                    pre.right = makeNew(cur);
                } else pre.left = makeNew(cur);
                break;
            } else if(cur.val > value){
                pre = cur;
                cur = cur.left;
            } else {
                pre = cur;
                cur = cur.right;
            }
        }
        return dummy.right;
    }
   
    private TreeNode makeNew(TreeNode node){
        if(node.left == null && node.right == null) return null;
        if(node.left == null || node.right == null) return node.left == null
            ? node.right : node.left;
        TreeNode leftMost = node.right;
        while(leftMost.left != null){
            leftMost = leftMost.left;
        }
        leftMost.left = node.left.right;
        node.left.right = node.right;
        return node.left;
    }
}