AVL Tree and MinHeap Java Implementations with Complexity

Posted on Feb 11, 2026 in Computer Engineering

AVL Tree Java Implementation

Balanced binary search tree (AVL) implementation in Java.

// AVLTree implementation
class AVLTree {
    class Node {
        int key, height;
        Node left, right;

        Node(int key) {
            this.key = key;
            this.height = 1;
        }
    }

    Node root;

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

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

    Node rotateRight(Node y) {
        Node x = y.left;
        Node t = x.right;

        x.right = y;
        y.left = t;

        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 rotateLeft(Node x) {
        Node y = x.right;
        Node t = y.left;

        y.left = x;
        x.right = t;

        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 insert(Node n, int key) {
        if (n == null)
            return new Node(key);

        if (key < n.key)
            n.left = insert(n.left, key);
        else if (key > n.key)
            n.right = insert(n.right, key);
        else
            return n;

        n.height = Math.max(height(n.left), height(n.right)) + 1;
        int b = balance(n);

        if (b > 1 && key < n.left.key)
            return rotateRight(n);

        if (b < -1 && key > n.right.key)
            return rotateLeft(n);

        if (b > 1 && key > n.left.key) {
            n.left = rotateLeft(n.left);
            return rotateRight(n);
        }

        if (b < -1 && key < n.right.key) {
            n.right = rotateRight(n.right);
            return rotateLeft(n);
        }

        return n;
    }

    Node minValue(Node n) {
        while (n.left != null)
            n = n.left;
        return n;
    }

    Node delete(Node r, int key) {
        if (r == null)
            return r;

        if (key < r.key)
            r.left = delete(r.left, key);
        else if (key > r.key)
            r.right = delete(r.right, key);
        else {
            if (r.left == null || r.right == null)
                r = (r.left != null) ? r.left : r.right;
            else {
                Node t = minValue(r.right);
                r.key = t.key;
                r.right = delete(r.right, t.key);
            }
        }

        if (r == null)
            return null;

        r.height = Math.max(height(r.left), height(r.right)) + 1;
        int b = balance(r);

        if (b > 1 && balance(r.left) >= 0)
            return rotateRight(r);

        if (b > 1 && balance(r.left) < 0) {
            r.left = rotateLeft(r.left);
            return rotateRight(r);
        }

        if (b < -1 && balance(r.right) <= 0)
            return rotateLeft(r);

        if (b < -1 && balance(r.right) > 0) {
            r.right = rotateRight(r.right);
            return rotateLeft(r);
        }

        return r;
    }

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

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

MinHeap Java Implementation

Simple fixed-capacity MinHeap implementation with bubble-up and bubble-down.

// MinHeap implementation
public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    private void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    private void bubbleUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    private void bubbleDown(int i) {
        int min = i;
        int l = leftChild(i);
        int r = rightChild(i);

        if (l < size && heap[l] < heap[min]) min = l;
        if (r < size && heap[r] < heap[min]) min = r;

        if (min != i) {
            swap(i, min);
            bubbleDown(min);
        }
    }

    public void insert(int val) {
        if (size == capacity) return;
        heap[size] = val;
        size++;
        bubbleUp(size - 1);
    }

    public int removeMin() {
        if (size == 0) return -1;
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        bubbleDown(0);
        return min;
    }

    public void printHeap() {
        for (int i = 0; i < size; i++)
            System.out.print(heap[i] + " ");
        System.out.println();
    }
}

Iterative Tree Traversals (Generic TreeNode)

Iterative preorder, postorder and inorder traversals using a stack.

// Iterative traversals using Stack>
public void preorder(TreeNode<E> root) {
    if (root == null) return;
    Stack<TreeNode<E>> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode<E> current = stack.pop();
        System.out.print(current.data + " ");
        if (current.right != null) stack.push(current.right);
        if (current.left != null) stack.push(current.left);
    }
}

public void postorder(TreeNode<E> root) {
    if (root == null) return;
    Stack<TreeNode<E>> stack = new Stack<>();
    Stack<TreeNode<E>> result = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode<E> current = stack.pop();
        result.push(current);
        if (current.left != null) stack.push(current.left);
        if (current.right != null) stack.push(current.right);
    }

    while (!result.isEmpty()) {
        System.out.print(result.pop().data + " ");
    }
}

public void inorder(TreeNode<E> root) {
    if (root == null) return;
    Stack<TreeNode<E>> stack = new Stack<>();
    TreeNode<E> current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.print(current.data + " ");
        current = current.right;
    }
}

Time Complexity Comparison

Comparison of average and worst-case complexities for BST, AVL tree and Min/Max heap operations.