Untitled

import java.util.*;

class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

public class Main {

    static Node root;

    // HEIGHT
    static int height(Node n) {
        return (n == null) ? 0 : n.height;
    }

    // MAX
    static int max(int a, int b) {
        return Math.max(a, b);
    }

    // BALANCE
    static int getBalance(Node n) {
        return (n == null) ? 0 : height(n.left) - height(n.right);
    }

    // RIGHT ROTATE
    static Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // LEFT ROTATE
    static Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // INSERT
    static Node insert(Node node, int key) {
        if (node == null)
            return new Node(key);

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else {
            System.out.println(key + " ignored. Duplicate value.");
            return node;
        }

        node.height = 1 + max(height(node.left), height(node.right));

        int balance = getBalance(node);

        // LL
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);

        // RR
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);

        // LR
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // MAX VALUE NODE (for left subtree — DRIFT RULE)
    static Node maxValueNode(Node node) {
        Node current = node;
        while (current.right != null)
            current = current.right;
        return current;
    }

    // KEY EXISTS CHECK
    static boolean keyExists(Node node, int key) {
        if (node == null) return false;
        if (key == node.key) return true;
        if (key < node.key) return keyExists(node.left, key);
        return keyExists(node.right, key);
    }

    // DELETE (DRIFT RULE: LEFT FIRST, THEN RIGHT)
    static Node delete(Node root, int key) {
        if (root == null)
            return root;

        if (key < root.key)
            root.left = delete(root.left, key);
        else if (key > root.key)
            root.right = delete(root.right, key);
        else {
            // Case 1: one child or no child
            if (root.left == null || root.right == null) {
                Node temp = (root.left != null) ? root.left : root.right;
                root = (temp == null) ? null : temp;
            }
            // Case 2: two children → APPLY DRIFT RULE
            else {
                // PRIORITY: LEFT SUBTREE → get MAX (predecessor)
                Node temp = maxValueNode(root.left);
                root.key = temp.key;
                root.left = delete(root.left, temp.key);
            }
        }

        if (root == null)
            return root;

        root.height = 1 + max(height(root.left), height(root.right));

        int balance = getBalance(root);

        // LL
        if (balance > 1 && getBalance(root.left) >= 0)
            return rightRotate(root);

        // LR
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // RR
        if (balance < -1 && getBalance(root.right) <= 0)
            return leftRotate(root);

        // RL
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    // PRINT TREE AS 1D ARRAY (0 for nulls, index-based BFS)
    static void printTree() {
        if (root == null) {
            System.out.println("\nTree Array: [0]");
            return;
        }

        int treeHeight = height(root);
        int size = (int) Math.pow(2, treeHeight) - 1;

        int[] arr = new int[size];

        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{root, 0});

        while (!q.isEmpty()) {
            Object[] pair = q.poll();
            Node node = (Node) pair[0];
            int idx = (int) pair[1];

            if (idx >= size) continue;
            arr[idx] = node.key;

            if (node.left != null)  q.add(new Object[]{node.left,  2 * idx + 1});
            if (node.right != null) q.add(new Object[]{node.right, 2 * idx + 2});
        }

        System.out.print("\nTree Array: [");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }

    // TRAVERSALS
    static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.key + " ");
            inorder(root.right);
        }
    }

    static void preorder(Node root) {
        if (root != null) {
            System.out.print(root.key + " ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    static void postorder(Node root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.key + " ");
        }
    }

    // PROCESS INSERT (comma-separated)
    static void processInsert(String line) {
        if (line.trim().isEmpty()) return;
        for (String p : line.trim().split(",")) {
            p = p.trim();
            if (p.isEmpty()) continue;
            try {
                root = insert(root, Integer.parseInt(p));
            } catch (NumberFormatException e) {
                System.out.println("'" + p + "' is not a valid integer. Skipped.");
            }
        }
    }

    // PROCESS DELETE (comma-separated)
    static void processDelete(String line) {
        if (line.trim().isEmpty()) return;
        for (String p : line.trim().split(",")) {
            p = p.trim();
            if (p.isEmpty()) continue;
            try {
                int val = Integer.parseInt(p);
                if (!keyExists(root, val))
                    System.out.println(val + " does not exist.");
                else {
                    root = delete(root, val);
                    System.out.println(val + " deleted.");
                }
            } catch (NumberFormatException e) {
                System.out.println("'" + p + "' is not a valid integer. Skipped.");
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean isInsert = true;

        System.out.println("Type 'print' to print the array.\n");

        while (true) {
            System.out.print(isInsert ? "Insert: " : "Delete: ");
            String line = sc.nextLine().trim();

            if (line.equalsIgnoreCase("print")) {
                printTree();
                
                System.out.print("Preorder:  ");
                preorder(root);
                System.out.println();

                System.out.print("Inorder:   ");
                inorder(root);
                System.out.println();

                System.out.print("Postorder: ");
                postorder(root);
                System.out.println("\n");
                break;
            }

            if (isInsert) processInsert(line);
            else processDelete(line);

            isInsert = !isInsert;
        }

        sc.close();
    }
}