package leetcode;

/**
 * https://leetcode.com/problems/delete-node-in-a-bst/
 */
public class Problem450 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return Integer.toString(val);
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        NodeRef ref = new NodeRef(root);
        deleteNode(root, null, Direction.MIDDLE, key, ref);
        return ref.node;
    }

    private enum Direction {
        LEFT, RIGHT, MIDDLE
    }

    private static class NodeRef {
        private TreeNode node;

        public NodeRef(TreeNode node) {
            this.node = node;
        }
    }

    private static void deleteNode(TreeNode node, TreeNode parent, Direction direction, int key, NodeRef ref) {
        if (node == null) {
            return;
        }
        if (key == node.val) {
            if (node.left == null && node.right == null) {
                if (parent != null) {
                    if (direction == Direction.LEFT) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                } else {
                    ref.node = null;
                }
            } else if (node.left == null && node.right != null) {
                if (parent != null) {
                    if (direction == Direction.LEFT) {
                        parent.left = node.right;
                    } else {
                        parent.right = node.right;
                    }
                } else {
                    ref.node = node.right;
                }
            } else if (node.left != null && node.right == null) {
                if (parent != null) {
                    if (direction == Direction.LEFT) {
                        parent.left = node.left;
                    } else {
                        parent.right = node.left;
                    }
                } else {
                    ref.node = node.left;
                }
            } else {
                TreeNode smallest = getSmallest(node.right, node, Direction.RIGHT);
                if (parent != null) {
                    if (direction == Direction.LEFT) {
                        parent.left = smallest;
                    } else {
                        parent.right = smallest;
                    }
                } else {
                    ref.node = smallest;
                }
                if (node.left != null) {
                    smallest.left = node.left;
                }
                if (node.right != null) {
                    smallest.right = node.right;
                }
            }
        } else if (key < node.val) {
            deleteNode(node.left, node, Direction.LEFT, key, ref);
        } else {
            deleteNode(node.right, node, Direction.RIGHT, key, ref);
        }
    }

    private static TreeNode getSmallest(TreeNode node, TreeNode parent, Direction direction) {
        if (node.left == null) {
            if (direction == Direction.LEFT) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            return node;
        }
        return getSmallest(node.left, node, Direction.LEFT);
    }

    private static TreeNode getLargest(TreeNode node, TreeNode parent, Direction direction) {
        if (node.right == null) {
            if (direction == Direction.LEFT) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            return node;
        }
        return getLargest(node.right, node, Direction.RIGHT);
    }

    public static void main(String[] args) {
        Problem450 prob = new Problem450();

//        TreeNode root = new TreeNode(5);
//        root.left = new TreeNode(3);
//        root.left.left = new TreeNode(2);
//        root.left.left.left = new TreeNode(1);
//        root.left.right = new TreeNode(4);
//        root.right = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//
//        root = prob.deleteNode(root, 3);
//        root = prob.deleteNode(root, 5);
//        root = prob.deleteNode(root, 1);
//        System.out.println(root);
//        System.out.println(root.left);
//        System.out.println(root.left.left);
//        System.out.println(root.left.left.left);
//        System.out.println(root.left.right);
//        System.out.println(root.right);
//        System.out.println(root.right.right);

//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(1);
//        root.left.right = new TreeNode(2);
//        root.right = new TreeNode(4);
//
//        root = prob.deleteNode(root, 1);
//        System.out.println(root);
//        System.out.println(root.left);
//        System.out.println(root.right);

        TreeNode root = new TreeNode(3);
        root.right = new TreeNode(5);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(10);
        root.right.right.left = new TreeNode(7);
        root.right.right.left.right = new TreeNode(8);
        root.right.right.left.right.right = new TreeNode(9);
        root.right.right.right = new TreeNode(11);

        root = prob.deleteNode(root, 5);
        System.out.println(root);
        System.out.println(root.right);
        System.out.println(root.right.right);
        System.out.println(root.right.right.left);
        System.out.println(root.right.right.left.right);
        System.out.println(root.right.right.right);

//        TreeNode root = new TreeNode(5);
//        root.right = new TreeNode(10);
//        root.right.left = new TreeNode(7);
//        root.right.right = new TreeNode(15);
//        root.right.right.left = new TreeNode(12);
//        root.right.right.left.right = new TreeNode(13);
//        root.right.right.right = new TreeNode(16);
//
//        root = prob.deleteNode(root, 15);
//        System.out.println(root);
//        System.out.println(root.right);
//        System.out.println(root.right.left);
//        System.out.println(root.right.right);
//        System.out.println(root.right.right.left);
//        System.out.println(root.right.right.left.right);
    }
}

@@ -261,114 +261,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return Integer.toString(val);%0A        %7D
 %0A   
@@ -3113,3122 +3113,190 @@
  = n
-ull;%0A            %7D else %7B%0A                parent.right = null;%0A            %7D%0A            return node;%0A        %7D%0A        return getSmallest(node.left, node, Direction.LEFT);%0A    %7D%0A%0A    private static TreeNode getLargest(TreeNode node, TreeNode parent, Direction direction) %7B%0A        if (node.right == null) %7B%0A            if (direction == Direction.LEFT) %7B%0A                parent.left = null;%0A            %7D else %7B%0A                parent.right = null;%0A            %7D%0A            return node;%0A        %7D%0A        return getLargest(node.right, node, Direction.RIGHT)
+ode.right;%0A            %7D else %7B%0A                parent.right = node.right
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem450 prob = new Problem450();%0A%0A//        TreeNode root = new TreeNode(5);%0A//        root.left = new TreeNode(3);%0A//        root.left.left = new TreeNode(2);%0A//        root.left.left.left = new TreeNode(1);%0A//        root.left.right = new TreeNode(4);%0A//        root.right = new TreeNode(6);%0A//        root.right.right = new TreeNode(7);%0A//%0A//        root = prob.deleteNode(root, 3);%0A//        root = prob.deleteNode(root, 5);%0A//        root = prob.deleteNode(root, 1);%0A//        System.out.println(root);%0A//        System.out.println(root.left);%0A//        System.out.println(root.left.left);%0A//        System.out.println(root.left.left.left);%0A//        System.out.println(root.left.right);%0A//        System.out.println(root.right);%0A//        System.out.println(root.right.right);%0A%0A//        TreeNode root = new TreeNode(3);%0A//        root.left = new TreeNode(1);%0A//        root.left.right = new TreeNode(2);%0A//        root.right = new TreeNode(4);%0A//%0A//        root = prob.deleteNode(root, 1);%0A//        System.out.println(root);%0A//        System.out.println(root.left);%0A//        System.out.println(root.right);%0A%0A        TreeNode root = new TreeNode(3);%0A        root.right = new TreeNode(5);%0A        root.right.left = new TreeNode(4);%0A        root.right.right = new TreeNode(10);%0A        root.right.right.left = new TreeNode(7);%0A        root.right.right.left.right = new TreeNode(8);%0A        root.right.right.left.right.right = new TreeNode(9);%0A        root.right.right.right = new TreeNode(11);%0A%0A        root = prob.deleteNode(root, 5);%0A        System.out.println(root);%0A        System.out.println(root.right);%0A        System.out.println(root.right.right);%0A        System.out.println(root.right.right.left);%0A        System.out.println(root.right.right.left.right);%0A        System.out.println(root.right.right.right);%0A%0A//        TreeNode root = new TreeNode(5);%0A//        root.right = new TreeNode(10);%0A//        root.right.left = new TreeNode(7);%0A//        root.right.right = new TreeNode(15);%0A//        root.right.right.left = new TreeNode(12);%0A//        root.right.right.left.right = new TreeNode(13);%0A//        root.right.right.right = new TreeNode(16);%0A//%0A//        root = prob.deleteNode(root, 15);%0A//        System.out.println(root);%0A//        System.out.println(root.right);%0A//        System.out.println(root.right.left);%0A//        System.out.println(root.right.right);%0A//        System.out.println(root.right.right.left);%0A//        System.out.println(root.right.right.left.right
+    %7D%0A            return node;%0A        %7D%0A        return getSmallest(node.left, node, Direction.LEFT
 );%0A 

Solve problem 450