<aside> 💡

Height-Balanced

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than on

</aside>

✅ 1. Binary Tree (Generic Structure)

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

✅ Use Case:


✅ 2. Binary Search Tree (BST)

class BST {
    TreeNode root;

    void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else node.right = insert(node.right, val);
        return node;
    }

    boolean search(int val) {
        return search(root, val);
    }

    private boolean search(TreeNode node, int val) {
        if (node == null) return false;
        if (val == node.val) return true;
        return val < node.val ? search(node.left, val) : search(node.right, val);
    }
}

⏱ Time:


✅ 3. AVL Tree (Self-balancing BST)

class AVLNode {
    int val, height;
    AVLNode left, right;
    AVLNode(int val) { this.val = val; height = 1; }
}

class AVLTree {
    AVLNode root;

    int height(AVLNode n) {
        return n == null ? 0 : n.height;
    }

    int getBalance(AVLNode n) {
        return n == null ? 0 : height(n.left) - height(n.right);
    }

    AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T = x.right;
        x.right = y;
        y.left = T;
        y.height = 1 + Math.max(height(y.left), height(y.right));
        x.height = 1 + Math.max(height(x.left), height(x.right));
        return x;
    }

    AVLNode rotateLeft(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T = y.left;
        y.left = x;
        x.right = T;
        x.height = 1 + Math.max(height(x.left), height(x.right));
        y.height = 1 + Math.max(height(y.left), height(y.right));
        return y;
    }

    AVLNode insert(AVLNode node, int val) {
        if (node == null) return new AVLNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        else return node;

        node.height = 1 + Math.max(height(node.left), height(node.right));
        int balance = getBalance(node);

        // 4 Rotations
        if (balance > 1 && val < node.left.val) return rotateRight(node);
        if (balance < -1 && val > node.right.val) return rotateLeft(node);
        if (balance > 1 && val > node.left.val) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        if (balance < -1 && val < node.right.val) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }
}

⏱ Time:


✅ 4. Red-Black Tree

📌 Use TreeMap / TreeSet in Java — internally implemented as Red-Black Tree.

TreeMap<Integer, String> map = new TreeMap<>();
TreeSet<Integer> set = new TreeSet<>();