Deletion In AVL Tree In Java

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

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

public class AVLDeletion {

    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

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

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

        return x;
    }

    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

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

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

        return y;
    }

    Node minValueNode(Node node) {
        Node current = node;
        while (current.left != null)
            current = current.left;
        return current;
    }

    Node delete(Node root, int key) {

        // Step 1: BST deletion
        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 {
            // Node with one or no child
            if ((root.left == null) || (root.right == null)) {
                Node temp = (root.left != null) ? root.left : root.right;

                if (temp == null) {
                    root = null;
                } else {
                    root = temp;
                }
            } else {
                // Node with two children
                Node temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = delete(root.right, temp.key);
            }
        }

        // If tree had only one node
        if (root == null)
            return root;

        // Step 2: Update height
        root.height = Math.max(height(root.left), height(root.right)) + 1;

        // Step 3: Get balance
        int balance = getBalance(root);

        // Step 4: Balance the tree

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

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

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

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

        return root;
    }

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

    public static void main(String[] args) {
        AVLDeletion tree = new AVLDeletion();
        Node root = null;

        int[] values = {10, 20, 30, 40, 50, 25};

        // Insert first (reuse insertion logic if needed)
        AVLInsertion insertHelper = new AVLInsertion();
        for (int val : values) {
            root = insertHelper.insert(root, val);
        }

        System.out.print("Before Deletion: ");
        tree.inorder(root);

        root = tree.delete(root, 40);

        System.out.print("\nAfter Deletion: ");
        tree.inorder(root);
    }
}