The balanced BST idea

Why it matters

Every fast operation on a binary search tree depends on one number: its height. A short tree makes search, insert and delete quick. A tall tree makes them slow, and a tree that is a straight line makes them as slow as a plain list. This lesson explains why that can happen to an ordinary BST, shows how to build a good tree when you have all the values in advance, and gives you the definition of a balanced tree that the next lesson turns into a working algorithm.

It also explains why the standard containers in C++ are safe to use. std::set and std::map keep their trees balanced, so they stay fast no matter what order the values arrive in. If you understand the problem they solve, you will know when to trust them and when to read their documentation carefully.

Start with a shelf of books

Imagine a library shelf where a new book is always placed at the far right end, after every book already there. If the books arrive in alphabetical order, the shelf is perfectly sorted, but finding a book means walking past all the earlier ones. The shelf works like a list, and its cost grows with the number of books.

A better shelf is organized in halves. The middle book sits at the centre of the shelf. Books on the left of it are alphabetically before it, and books on the right are after it. Each half is organized the same way. To find a book, you look at the centre, and then you walk to one half. This is the shape a balanced tree gives you.

A binary search tree is a shelf of this kind, but it grows from the order in which books arrive. If the arrivals are random, the tree stays roughly balanced. If the arrivals are sorted, the tree becomes the bad shelf again, and every new book goes to the far end.

The problem with a plain BST

Insert the values 1, 2, 3, 4, 5, 6 and 7 into a plain BST, one after another. Each new value is larger than all the values before it, so each one goes to the right of the last. The result is a chain:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

The chain has height 7. A search for 7 visits all seven nodes. A search for any value visits every node above it. In general, a chain of n nodes has height n, so operations cost O(n), the same as a plain array scan. The sorted order is still there, and the inorder walk still prints 1 to 7, but the tree has lost the speed that made it worth building.

This happens in real data more often than you might think. Timestamps arrive in time order. Auto-increment IDs arrive in increasing order. Scores in a leaderboard often arrive in rising order. A program that stores these values in a plain BST can slow down in production, while the same code looks fine in a test that uses random numbers. That is the trap: random test data hides the problem.

Here is a program that shows the difference. It builds a balanced tree and a plain tree from the same sorted values, then prints both heights. The input is the number of values and the values themselves, which are sorted.

Type this into the Input box:

7
1 2 3 4 5 6 7

The output is:

balanced height: 3
plain BST height: 7

Try it with a larger sorted input, such as 20 values from 1 to 20. The balanced height grows to 5, and the plain height grows to 20. Each time the number of values doubles, the balanced height grows by one, but the plain height doubles. That difference is the whole reason for this lesson.

Balanced: what the word means

A tree is height-balanced when, for every node, the heights of its left subtree and its right subtree differ by at most 1. The word is about each node, not only the root. A tree can have a balanced root and still have an unbalanced node further down, so you must check every node.

The tree built from 1 to 7 is height-balanced. The root 4 has left and right subtrees of height 2, which differ by 0. Node 2 has two children, so its subtrees differ by 0. Node 6 is the same. The leaves have empty subtrees of height 0, which differ by 0.

A tree can be height-balanced without being perfect. A perfect tree has every level full. A balanced tree may leave the last level partly empty, as long as no subtree is too tall compared with its sibling.

The important fact is that a height-balanced tree with n nodes has height about log2 n. Here is why. A tree of height h can hold at most 2 to the power h minus 1 nodes, because each level has twice as many slots as the level above it. So with n nodes, you need at least h levels where 2 to the power h is larger than n. Taking the base-2 logarithm gives h of about log2(n + 1). For n = 1,000,000, the answer is about 20.

Build a balanced BST from a sorted array

If you already have the values in a sorted array, you can build a balanced tree directly, without inserting one at a time. The rule is simple. Pick the middle element as the root. Everything before the middle goes into the left subtree, and everything after it goes into the right subtree. Repeat the same rule on each half.

Choosing the middle keeps the two halves almost the same size. The left half and the right half differ in size by at most one element, so their heights differ by at most one. Applying the same choice at every level keeps every node balanced.

This is the same halving idea as binary search. The next picture shows the search, and you can compare each step with the choice of root. The middle of the current range is the value the search tests, and the middle of the same range is the root of the tree.

Watch the middle index in the search. Each step picks the middle of the current range, and the range is cut in half. The tree build does the same thing: it picks the middle of the range, makes it the root, and then builds the two halves. The only difference is that the build does not stop at one value. It keeps the middle at every level, so each value becomes a node.

Here is the build function from the first program, shown again by itself.

Node* build(const vector<int>& a, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = lo + (hi - lo) / 2;
    Node* n = new Node(a[mid]);
    n->left = build(a, lo, mid - 1);
    n->right = build(a, mid + 1, hi);
    return n;
}

The base case lo > hi means the range is empty, and the function returns nullptr. The middle index is computed as lo + (hi - lo) / 2. That form avoids overflow when lo and hi are both large. A shorter form, (lo + hi) / 2, can overflow when the sum is larger than the largest int. With arrays of ordinary size, the two forms agree, but the safe form is the habit to build.

The function creates one node for every element, and each element is visited once. So the time is O(n). The recursion goes down about log n levels before it reaches empty ranges, so the call stack uses O(log n) memory. The tree itself uses O(n) memory.

Here is the same idea on the array 1 through 7, with the output of a preorder walk. Preorder visits the node first, then the left subtree, then the right subtree. It shows the shape clearly.

The output is:

4 2 1 3 6 5 7 
height: 3

Trace the first call. The range is indexes 0 to 6, so the middle is index 3, which holds 4. The function makes 4 the root. The left range is indexes 0 to 2, with middle index 1 holding 2. The right range is indexes 4 to 6, with middle index 5 holding 6. The next level gives 1 and 3 under 2, and 5 and 7 under 6. Preorder prints the root first, so the output starts with 4, then 2, then the left leaves 1 and 3, then 6, 5 and 7.

If the array had an even length, such as , the middle is the lower of the two middle values, which is 2 in this case, because lo + (hi - lo) / 2 rounds down. You could also round up. Either choice gives a balanced tree. Practice exercise 8 asks you to work out the difference.

Build by hand: ten values

Follow the build on paper for the values 1 to 10. They sit at indexes 0 to 9 of the array.

The first call has lo = 0 and hi = 9. The middle is 0 + (9 - 0) / 2, which is 4, and that index holds 5. So 5 is the root. The left range is indexes 0 to 3, and the right range is indexes 5 to 9.

Take the left range first. Its middle is 0 + (3 - 0) / 2, which is 1, and that index holds 2. So 2 is the left child of 5. Its own left range is index 0 alone, which holds 1. Its right range is indexes 2 to 3, whose middle is 2 + (3 - 2) / 2, which is 2. That index holds 3, and the last range, index 3 alone, holds 4, the right child of 3.

Now the right range, indexes 5 to 9. Its middle is 5 + (9 - 5) / 2, which is 7, and that index holds 8. So 8 is the right child of 5. Its left range is indexes 5 to 6, whose middle is 5, which holds 6, and the single index 6 holds 7 as the right child of 6. Its right range is indexes 8 to 9, whose middle is 8, which holds 9, and index 9 holds 10 as the right child of 9.

The finished tree has 5 at the root, with a left subtree of 2 (children 1 and 3, and 3 has right child 4) and a right subtree of 8 (children 6 and 9, with 6 holding 7 on its right and 9 holding 10 on its right). Its preorder is 5 2 1 3 4 8 6 7 9 10, and its height is 4.

Ten values fit into height 4, which matches the formula. The formula gives the ceiling of log2(10 + 1), which is 4. Both subtrees of the root have height 3, so the root is perfectly balanced here. The middle rule guarantees that the two halves differ in size by at most one value, and that is what keeps the heights within one of each other at every level.

Checking whether a tree is balanced

Sometimes a tree already exists and you need to check whether it is balanced. The definition gives you a direct method: for every node, compute the heights of the two subtrees and compare them. The naive version does this at every node, which means computing heights many times over. Its cost is O(n^2) in a chain, because each height call walks down the whole chain.

A better method computes the height and the check together. The function returns the height of a subtree if the subtree is balanced, and it returns -1 as soon as it finds an unbalanced node. The parent then stops at once. Each node is visited exactly once, so the cost is O(n).

The output is:

tree A: balanced, height 3
tree B: not balanced

Tree B is short on the right and tall on the left. At the root, the left side has height 3 and the right side has height 0. The difference is 3, which is more than 1, so the root is not balanced. The function returns -1 at the root, and isBalanced returns false.

Notice the return value of -1. Heights are never negative, so -1 is a safe signal. It does mean the function cannot return a real height of -1, which is fine here.

Self-balancing trees

Building a balanced tree from a sorted array needs all the values at once. Real programs add and remove values over time, and they cannot rebuild the whole tree after each change. For that case, we need a tree that repairs its own shape with small local changes. Such a tree is called self-balancing.

The local change is called a rotation. A rotation moves a few links around one node, so that a tall side becomes shorter, and the order of the values does not change. Lesson 5 shows the first and simplest self-balancing tree, the AVL tree, with its rotations.

Two families matter in practice:

The red-black tree allows a little more height in exchange for fewer rotations. Insert and delete are cheaper, which is why library authors chose it. You do not need to implement either tree to use std::map or std::set, but you do need to know that they are balanced, so their operations are O(log n) no matter what order you add values in.

The next program uses std::set, the standard balanced container, to answer the successor question from lesson 3. It takes values in any order, which is exactly the situation where a plain BST would fail. Type this into the Input box:

7
8 3 10 6 14 8 7
4
6
7
14
5

The output is:

stored: 3 6 7 8 10 14
7
8
none
6

The input contains the value 8 twice. The set keeps one copy, so the stored list has six values. The query upper_bound(x) returns an iterator to the first value strictly greater than x. The answers match lesson 3: the successor of 6 is 7, the successor of 7 is 8, nothing follows 14, and the successor of 5 is 6. The set does the work of the balanced tree for you. Its cost per operation is O(log n) in every case.

Red-black trees in more detail

A red-black tree is a BST where each node carries one extra bit: its colour, which is either red or black. Four rules keep the shape from drifting too far. The root is black. A red node never has a red child. Every path from a node down to an empty link passes through the same number of black nodes. Empty links count as black. Together these rules guarantee that the longest path from the root is at most about twice the shortest path, which gives a height of at most about 2 log2(n + 1).

When you insert or delete, the tree may break one of these rules. The repair is a short sequence of recolourings and rotations, and it touches only a few nodes near the change. A red-black tree may be a little taller than an AVL tree, because it allows a bigger gap between paths. In exchange, it does fewer rotations on average, so frequent updates cost less. That trade is why many libraries chose it. You do not need to implement one to use std::map, but if an interviewer asks why it is fast, these four rules are the core of the answer.

Building from unsorted input

The build needs a sorted array. If the values arrive in any order, sort them first. Sorting costs O(n log n), which is more than the O(n) build, so the total cost is O(n log n). After the sort, the build itself is linear. This is often the right choice for a batch of values that you will search many times: sort once, build once, then answer many queries.

For values that keep arriving one at a time, rebuilding after every value would cost too much. Use a self-balancing tree instead, as the next lesson shows. A built tree does not follow changes to the array behind it, so if the array changes, you must rebuild the tree or switch to an insert-based structure.

Complexity: sorted input changes everything

The table compares the two kinds of tree on the same input.

The "expected" in the first row means on average over random input. A plain tree with random order is usually balanced enough, but there is no guarantee. Building from a sorted array in O(n) is possible only because you know all the values in advance and can choose the middle directly.

For a million sorted values, inserting one at a time into a plain BST costs about a million steps for each insert, which adds up to about 5 times 10 to the power 11 steps for the whole build. Building directly from the sorted array takes about a million steps in total.

What happens inside: recursion depth

The build uses recursion. Each call splits its range in half and calls itself on each half. The depth of the recursion is the number of times you can halve the range before it is empty, which is about log n. So the call stack is about 20 frames deep for a million values, and the extra memory is tiny.

The plain BST insert is different. When the input is sorted, each insert goes down the whole chain before it stops, so the recursion depth grows to n. That is why a plain BST with a million sorted values can crash. Here is the real output of a plain-BST program run on sorted input of different sizes:

height 10000
exit 0

That is for 10,000 values, which runs fine. For 1,000,000 values the same program prints nothing and ends with exit code 139. Exit code 139 means the program was killed by a segmentation fault, which is what happens when the call stack runs out of space. The recursion needed a million frames, and the default stack on most Linux systems is 8 MB. The fix is not a bigger stack. The fix is a balanced tree, so that the depth stays near log n.

Common mistakes and the messages you will see

Mistake 1: using the first element as the root. If you write int mid = lo;, the root is always the smallest value. The left range is empty, and the right range is everything else, so the tree becomes a chain. The program runs without an error, and it prints a height of n. Always choose a middle index.

Mistake 2: an off-by-one in the upper bound. The last valid index of an array of size n is n - 1. If you call build(a, 0, a.size()), the middle can become index n, which is past the end of the array. With the standard vector check active, the program stops with an assertion:

Assertion '__n < this->size()' failed.

Under the address sanitizer, the same mistake is reported as a heap-buffer-overflow. The fix is to pass a.size() - 1, cast to int, as the programs in this lesson do.

Mistake 3: forgetting the base case. If build does not check lo > hi, it keeps calling itself on empty ranges and never stops. The call stack fills up, and the program crashes. The base case is the first line of the function.

Mistake 4: assuming the checker is cheap. The naive balance check computes the height at every node. On a chain of n nodes, the cost is O(n^2). Use the combined function, which returns -1 as soon as it finds a problem.

Mistake 5: confusing balanced with perfect. A balanced tree may not be full. A tree of seven nodes is perfect. A tree of six nodes is balanced, but it is not perfect. Code that checks for perfection rejects valid balanced trees.

Debugging walkthrough: a tree that should be balanced but is not

Suppose you build a tree from a sorted array of 10 values, and the balance check says it is unbalanced. First print the height of each subtree at the root, then move down the tree and print the heights at each node that fails. The printed numbers show you exactly which node is wrong.

A common cause is a wrong middle. If the build chose lo as the middle, the left side is empty and the right side has nine values. The printed heights at the root would be 0 and 4, which differs by more than 1. Once you see that pattern, you know the middle index is wrong.

Another cause is a wrong range, where build passes mid to a child instead of mid - 1. Then the same value appears twice, and the tree has more nodes than the array. Count the nodes in the tree and compare the count with the array size. A mismatch points to the range bounds.

Variations and edge cases

An empty array builds an empty tree, because the first call has lo = 0 and hi = -1, and lo > hi is true. Use (int)a.size() - 1 so that the value of hi is -1 when the array is empty. Note that a.size() - 1 without the cast gives a very large unsigned number, which breaks the comparison.

One value builds a single node.

Even-sized arrays have two possible middles. Both give balanced trees. Choose one, and keep it the same everywhere.

Duplicates in the array can be removed first with sorting and unique, or kept, which needs the duplicate rule from lesson 3. Practice exercise 6 asks you to remove them.

A sorted linked list can also become a balanced tree. You cannot index into a linked list, so you find the middle with two pointers, one moving one step at a time and one moving two steps. Practice exercise 3 asks you to write it.

Interview questions and real-world use

A common question is "convert a sorted array to a height-balanced BST". Write the build function, explain the middle choice, and say that it is O(n) in time and O(log n) in extra stack memory. Then say what changes for a linked list.

The second common question is "check whether a tree is balanced". Explain the definition, write the combined function, and mention the O(n^2) cost of the naive version. Good answers say why the -1 signal makes the check stop early.

In real systems, sorted input is common. Log files, timestamps and sequence numbers all arrive in order. Database indexes and sorted maps are built to stay balanced, because a plain tree would degrade on exactly that data. Knowing this lets you choose the right container, and it explains why a library's std::map is slower on a single insert than a plain BST but much faster in the worst case.

Common follow-up questions

Is balancing needed when the input is random? Not for every purpose. The expected height of a plain BST built from random values grows in proportion to log n, so a random insert order usually gives a tree that is good enough. The reason to balance anyway is the worst case. Sorted input, nearly sorted input and adversarial input all break the random assumption, and a single bad input can make every later operation slow. A balanced tree removes the dependence on the input order, so its cost is the same for every input.

What if the array has an odd number of values? The middle is unique, and removing it leaves an even number of values. The two halves are exactly the same size, so the root's subtrees have the same height, and the tree is balanced. The even case is where a choice exists, as practice exercise 8 shows.

How do you test a builder? Build from several arrays, including empty, one value, two values, a power of two minus one, and a power of two. For each tree, check three things: the inorder walk equals the input, the height equals the formula from this lesson, and the balance check passes. Those three checks together catch the common mistakes, such as a missing base case or a wrong range.

Practice

Try these before you open the solutions. Compile with g++ -std=c++17 -Wall -g -fsanitize=address,undefined.

1. Easy. Build a balanced BST from the sorted array using the middle rule that the lesson uses. Which value is the root? Draw the tree and state its height.

2. Easy. Check whether this tree is balanced: root 5, left child 3 with left child 2, and right child 8. Explain your answer with the heights at the root.

3. Medium. Write Node* sortedListToBST(ListNode* head), where the input is a sorted singly linked list. You may copy the values into a vector first. Hint: count the list, then build from the vector.

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
 
Node* buildRange(const vector<int>& a, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = lo + (hi - lo) / 2;
    Node* n = new Node(a[mid]);
    n->left = buildRange(a, lo, mid - 1);
    n->right = buildRange(a, mid + 1, hi);
    return n;
}
 
Node* sortedListToBST(ListNode* head) {
    vector<int> a;
    for (ListNode* p = head; p; p = p->next) a.push_back(p->val);
    return buildRange(a, 0, (int)a.size() - 1);
}

4. Medium. What is the smallest possible height of a tree with n nodes? Give a formula.

5. Medium. Write int countUnbalancedNodes(Node* root) that returns how many nodes have subtree heights differing by more than 1. Hint: one function computes heights and counts the bad nodes as it goes.

int countBad(Node* n, int& bad) {
    if (!n) return 0;
    int lh = countBad(n->left, bad);
    int rh = countBad(n->right, bad);
    if (abs(lh - rh) > 1) bad++;
    return 1 + max(lh, rh);
}
 
int countUnbalancedNodes(Node* root) {
    int bad = 0;
    countBad(root, bad);
    return bad;
}

6. Medium. Write Node* buildUnique(vector<int> a) that sorts the vector, removes duplicates, and builds a balanced BST. Hint: std::sort and std::unique with erase do the first two steps.

Node* buildUnique(vector<int> a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    return build(a, 0, (int)a.size() - 1);
}

7. Medium. Write the naive balance check bool isBalancedNaive(Node* root) that calls a height function at every node. Then state its cost on a chain of n nodes.

int heightOf(Node* n) {
    if (!n) return 0;
    return 1 + max(heightOf(n->left), heightOf(n->right));
}
 
bool isBalancedNaive(Node* n) {
    if (!n) return true;
    if (abs(heightOf(n->left) - heightOf(n->right)) > 1) return false;
    return isBalancedNaive(n->left) && isBalancedNaive(n->right);
}

8. Medium. For a sorted array of even length, the lower middle is lo + (hi - lo) / 2. Write the upper-middle version lo + (hi - lo + 1) / 2, and explain for the array what root each version picks.

9. Hard. Prove that a tree built by the middle rule from n sorted values has height exactly ceil(log2(n + 1)). Give a short argument.

10. Hard. Count the number of different binary search trees that can hold the keys 1 to n, where the shape matters and the values are fixed. Write the recurrence and the code. Check your code for n = 1 to 5.

#include <iostream>
#include <vector>
using namespace std;
 
long long countTrees(int n) {
    vector<long long> C(n + 1, 0);
    C[0] = 1;
    for (int m = 1; m <= n; m++) {
        for (int i = 0; i < m; i++) C[m] += C[i] * C[m - 1 - i];
    }
    return C[n];
}
 
int main() {
    for (int n = 1; n <= 5; n++) cout << countTrees(n) << " ";
    cout << "\n";
    return 0;
}

What you now know

• A plain BST degrades into a chain when the input is sorted, and then its operations cost O(n).
• A balanced tree has heights that differ by at most 1 at every node, and its height is about log n.
• Build a balanced tree from a sorted array by making the middle element the root, and recurse on each half.
• Check balance in one pass by returning -1 as soon as a node fails.
• Self-balancing trees repair their shape after each change, using rotations.
• The standard std::set and std::map are balanced, so their operations stay O(log n) on any input order.

The next lesson shows the first self-balancing tree, the AVL tree, and walks through its rotations.