Why Balance Matters

Same values, different shapes

The shape of a BST depends on the order you insert values. Insert them in a mixed order and the tree is bushy and short. Insert them already sorted and every node goes right – the “tree” is really a linked list:

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

public class Main {
    static Node insert(Node node, int v) {
        if (node == null) return new Node(v);
        if (v < node.value) node.left = insert(node.left, v);
        else if (v > node.value) node.right = insert(node.right, v);
        return node;                       // duplicates are ignored
    }

    static int height(Node n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }

    public static void main(String[] args) {
        int[] mixed = {4, 2, 6, 1, 3, 5, 7};
        int[] sorted = {1, 2, 3, 4, 5, 6, 7};
        Node a = null, b = null;
        for (int v : mixed) a = insert(a, v);
        for (int v : sorted) b = insert(b, v);
        System.out.println("mixed order height:  " + height(a));
        System.out.println("sorted order height: " + height(b));
    }
}

Output

mixed order height:  3
sorted order height: 7

Self-balancing trees

Clever BSTs (red-black trees, AVL trees) do small “rotations” after each insert to stay bushy, so their height is always about log n. You don't need to write one – Java already gives you a red-black tree inside TreeSet and TreeMap.

Think of it like this: A bookshelf that someone tidies after every new book, so you never end up with one impossibly tall stack.