Binary Search Tree

Scratch.java

class Scratch {


    public static TreeNode bst(TreeNode root, int key) {
        System.out.print(root.val + " -> ");
        if (root == null || root.val == key) {
            return root;
        }

        if (root.val > key) {
            return bst(root.left, key);
        }

        return bst(root.right, key);
    }

    public static TreeNode insert(TreeNode root, int key) {
        return insertRec(root, key);
    }

    public static TreeNode delete(TreeNode root, int key) {
        return deleteRec(root, key);
    }

    public static TreeNode deleteRec(TreeNode root, int key) {
        if (root == null) {
            return root;
        }

        if (key < root.val) {
            root.left = deleteRec(root.left, key);
        } else if (key > root.val) {
            root.right = deleteRec(root.right, key);
        }
        // if key is the same as root.val – it's node to be deleted
        else {
            //only 0 or 1 child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with 2 children: get inorder successor
            // (smallest in the right subtree)
            root.val = minValue(root.right);
            //delete the inorder successor
            root.right = deleteRec(root.right, root.val);
        }
        return root;
    }

    public static int minValue(TreeNode root) {
        int minValue = root.val;
        while (root.left != null) {
            minValue = root.left.val;
            root = root.left;
        }
        return minValue;
    }

    public static TreeNode insertRec(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }
        if (key < root.val) {
            root.left = insertRec(root.left, key);
        }
        else if (key > root.val) {
            root.right = insertRec(root.right, key);
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode l1 = new TreeNode(5);
        TreeNode l21 = new TreeNode(3);
        TreeNode l22 = new TreeNode(6);
        TreeNode l31 = new TreeNode(2);
        TreeNode l32 = new TreeNode(4);
        TreeNode l33 = new TreeNode(7);

        l21.left = l31;
        l21.right = l32;

        l22.left = null;
        l22.right = l33;

        l1.left = l21;
        l1.right = l22;

        bst(l1, 7);
        TreeNode inserted = insert(l1, 10);
        TreeNode afterDelete = delete(inserted, 6);
        System.out.println("Some print");
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}