Check whether a binary tree is height-balanced (every node's subtrees differ in height by at most 1).

Recurse and return the height of each subtree, or a sentinel such as -1 if it is unbalanced. At each node, if either child reports -1 or the heights differ by more than 1, return -1; otherwise return 1 + max of the heights. This visits every node once, so it is O(n) time and O(h) stack space. The naive version that recomputes heights at every node is O(n²) for a skewed tree.

Convert a sorted array into a height-balanced BST.

Pick the middle element as the root, then build the left subtree from the left half and the right subtree from the right half, recursively. The two halves differ in size by at most one, so heights differ by at most one. Time is O(n) and stack space is O(log n). The tree itself takes O(n). From a sorted linked list, count the nodes first and then build the tree in-order, bottom-up, so each list node is consumed once in O(n). Finding the middle with two pointers at every level also works but costs O(n log n).

Explain the four AVL rotation cases and draw the left-right case.

If a node z has balance factor +2 (left-heavy): when its left child's factor is 0 or +1, rotate right at z (left-left). If the left child's factor is -1, rotate left at the child first and then right at z (left-right). The right-heavy cases are the mirror images. Each rotation is O(1), insert needs at most two rotations, and the in-order order never changes. A delete can need more rotations because rebalancing a subtree may shrink its height, which then unbalances its parent, and the repair may repeat all the way up to the root (O(log n) levels).

Why do standard libraries use red-black trees more than AVL trees?

An AVL tree is more strictly balanced, so lookups are slightly faster, but inserts and deletes may rotate more. A red-black tree allows a taller tree (up to twice the shortest path) and needs at most 2 rotations for an insert and 3 for a delete, so write-heavy workloads suffer less. Both are O(log n) for every operation. Databases use B-trees instead, because wide nodes mean fewer disk reads.

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. Name each rotation and draw the final tree.

30 arrives and node 10 is -2 with a right-heavy child, so rotate left at 10 (right-right): 20 is the root with children 10 and 30. 40 and then 50 arrive and node 30 becomes -2 with a right-heavy child, so rotate left at 30: 40 has children 30 and 50. 25 goes under 30, node 20 becomes -2, and its heavy child 40 leans left (+1), so this is right-left: rotate right at 40, then left at 20. The final tree has root 30, left child 20 (children 10 and 25) and right child 40 (right child 50). That is 4 rotations and a height of 3.

How does a balanced tree answer "the smallest key at least x" and "all keys between a and b"?

For the smallest key at least x (the ceiling), walk down from the root: go left when the node is at least x and remember it, go right otherwise. The last remembered node is the answer in O(log n). For a range, find the ceiling of a, then repeatedly move to the in-order successor until the key passes b. That costs O(log n + k) for k results. A hash table cannot do either without scanning every key.

Balanced Trees

advanced · 30 min · Last reviewed 31 Oct 2026 · by TheLearningLoop Team

Key takeaways

A plain BST becomes a line when keys arrive sorted. A self-balancing tree rotates after inserts and deletes to keep the height O(log n).
The AVL rule: at every node the left and right heights differ by at most 1. Four cases (left-left, right-right, left-right, right-left) are fixed with one or two rotations.
A rotation changes the shape but never the in-order order of keys. AVL trees search faster, and red-black trees update with fewer rotations.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use a balanced tree

Use a balanced search tree when you need:

Ordered data that changes: insert, delete and search in O(log n) while keeping everything sorted.
Guaranteed O(log n) even for bad input such as already-sorted data, where a plain binary search tree degrades to O(n).
Ordered queries a hash map cannot answer: the next larger key, the previous smaller key, everything in a range, or the k-th smallest.

Use something else when:

You only need exact lookups: use a hash table, which is O(1) on average.
The data is built once and then only read: a sorted array with binary search is simpler and faster.
The data lives on disk: use a B-tree, which packs many keys per node to cut disk reads.
You only need the smallest or largest item: use a heap.

Do not write your own balanced tree in production. Use TreeMap, std::map or the like (see the real-world section). Writing an AVL tree by hand is for learning and interviews.

How a balanced tree works

A plain binary search tree keeps smaller keys on the left and larger keys on the right, which makes search fast only while the tree is short. Insert keys in sorted order and every new key goes to the right, so the tree becomes a straight line and every search costs O(n).

Intuition. Think of a phone book. You open it in the middle and halve the pages again and again, and that only works because the names are spread evenly. Now imagine every new name is stapled on at the end, in alphabetical order. The book is one long chain and you must read from the front. A balanced tree is a phone book that re-spreads itself as names arrive.

Here is the problem in three inserts. Put 1, 2 and 3 into a plain tree and you get a line:

1
 \
  2
   \
    3        height 3, a straight line

A balanced tree turns the same keys into this, with the same left-to-right order 1, 2, 3:

  2
 / \
1   3        height 2

A self-balancing tree repairs itself after each insert or delete so its height stays about log n. The repair is a rotation: re-linking a few nodes to move a subtree up one level without breaking the ordering rule.

AVL rule: at every node, the heights of the left and right subtrees differ by at most 1. The difference is called the balance factor and is always -1, 0 or +1.

Counting convention. The height of an empty subtree is 0 and the height of a leaf is 1. The balance factor of a node is the height of its left subtree minus the height of its right subtree. So +2 means "too heavy on the left" and -2 means "too heavy on the right".

If an insert makes a balance factor +2 or -2, a rotation (or two) restores it. A rotation touches only a few nodes, so it costs O(1). After the repair, the rebalanced subtree has the same height it had before the insert, so no node higher up changes and nothing more needs fixing. That is why an insert causes at most one rebalancing: either a single rotation or a double rotation (two rotations).

There are two common families:

AVL trees keep the strictest balance. Height is at most about 1.44 × log2(n), so searches are fastest, and inserts do slightly more rotating.
Red-black trees keep a looser rule using node colours (red or black) so that the longest path is at most twice the shortest. They rotate less on inserts and deletes, so updates are cheaper. Java's TreeMap and C++'s std::map typically use them.

Try it

Insert the same numbers into a plain tree and an AVL tree and compare the heights.

Balanced Trees

Step 1 of 17 · Press Space to play, arrow keys to step

TreeInsert order

The tree is empty.

Initial state. Insert 1, 2, 3, 4, 5, 6, 7 one at a time into an AVL tree. Watch the height.

step:: 0
height:: 0
rotations:: 0
comparisons:: 0
nodes:: 0

Speed

Things to try:

Choose Plain binary search tree and 1 2 3 4 5 6 7 (sorted). The height grows to 7: a straight line, so a search may take 7 comparisons.
Choose AVL tree with the same input. After 3 inserts it rotates, and at the end the height is 3 with 4 rotations in all. Every search takes at most 3 comparisons.
Choose AVL tree and 30 10 20 50 40 60. Inserting 20 makes a zig-zag, which needs a double rotation: first straighten, then rotate. The tones show which node is out of balance and which becomes the new top. Over the whole run the tree rotates 5 times: two double rotations (when 20 and 40 arrive) and one single rotation (when 60 arrives). The final height is 3.
Choose AVL tree and 4 2 6 1 3 5 7. No rotation is needed and the height is 3. The insert order matters more than the tree type, but only the AVL tree is safe for every order.

What to watch. Before you press Next on an "out of balance" step, work out the balance factors yourself: height of the left subtree minus height of the right subtree. Then predict which of the four cases it is and whether one or two rotations follow. Compare your answer with the caption.

Balanced tree operations: search, insert, delete and rotate

Search. The same as in a plain BST: go left if the target is smaller, right if larger. Height is O(log n), so this is O(log n).

Insert. Insert like a plain BST, then walk back up to the root, updating heights. At the first node whose balance factor is +2 or -2, rotate. One rotation (or one double rotation) restores the balance for the whole tree.

Delete. Delete like a plain BST, then walk back up, updating heights and rotating wherever the balance is broken. Unlike insert, a delete may need a rotation at several levels, still O(log n) in total.

The four imbalance cases (the node z is out of balance):

Left-left (left child is heavy on its left): rotate right at z.
Right-right (right child is heavy on its right): rotate left at z.
Left-right (left child is heavy on its right): rotate left at the child, then right at z.
Right-left (right child is heavy on its left): rotate right at the child, then left at z.

A rotation keeps the in-order sequence unchanged. This is the interview fact: it only changes shape, never the order of keys, which is why the tree is still a valid search tree afterwards.

Worked example: reading and fixing an imbalance by hand

The recipe is always the same. Walk back up from the new leaf, find the first node z with balance factor +2 or -2, then look at the balance factor of its heavy child. Same sign on both: one rotation. Opposite signs: two.

Example A: insert 10, 20, 30. After 30 is added the tree is a line, and node 10 has balance factor 0 - 2 = -2. Its heavy child, 20, has factor -1: same side, so this is right-right. Rotate left at 10.

10                 20
  \               /  \
   20     -->    10    30
     \
      30

Example B: insert 30, 10, 20. After 20 is added, node 30 has factor 2 - 0 = +2. Its heavy child, 10, has factor -1: opposite sides, so this is left-right. First rotate left at 10, which straightens the zig-zag into a line. Then rotate right at 30.

    30             30              20
   /              /               /  \
 10      -->    20       -->    10    30
   \           /
    20        10

In both examples the in-order sequence is 10, 20, 30 before and after. Only the shape changed.

Example C: a longer run. Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. The tree rotates when 30 arrives (right-right at 10), when 50 arrives (right-right at 30) and when 25 arrives (right-left at 20, a double rotation). That is 4 rotations in total and the final tree has root 30, with 20 (children 10 and 25) on the left and 40 (right child 50) on the right. Its height is 3, where a plain tree would have a height of 5 for the first five keys alone.

Balanced tree time complexity

Operation	Plain BST (average)	Plain BST (worst)	AVL tree	Red-black tree
Search	O(log n)	O(n)	O(log n)	O(log n)
Insert	O(log n)	O(n)	O(log n), at most 2 rotations	O(log n), at most 2 rotations
Delete	O(log n)	O(n)	O(log n), up to O(log n) rotations	O(log n), at most 3 rotations
Height	Average search path about 1.39 log2 n for random data	n	At most about 1.44 log2 n	At most 2 log2 (n + 1)
Space	O(n)	O(n)	O(n) plus a height or factor per node	O(n) plus a colour bit per node

n is the number of keys. The worst case of a plain BST happens when keys arrive sorted. Balancing removes it at the cost of a small extra field per node and a few rotations.

Why the height is logarithmic. Ask how few nodes an AVL tree of height h can have. The sparsest one has a root, one subtree of height h - 1 and one of height h - 2, so its size is N(h) = N(h-1) + N(h-2) + 1. That grows like the Fibonacci numbers, which is exponential in h. So n nodes force h to be at most about 1.44 × log2(n), never close to n.

Balanced trees vs other data structures

Job	AVL / red-black tree	Plain BST	Hash table	Sorted array	Skip list
Exact lookup	O(log n)	O(n) worst	O(1) average	O(log n)	O(log n)
Insert	O(log n) guaranteed	O(n) worst	O(1) average	O(n)	O(log n)
Delete	O(log n) guaranteed	O(n) worst	O(1) average	O(n)	O(log n)
In-order walk	O(n)	O(n)	O(n log n), must sort	O(n)	O(n)
Next larger / smaller key	O(log n)	O(n) worst	O(n)	O(log n)	O(log n)
Range query	O(log n + k)	O(n) worst	O(n)	O(log n + k)	O(log n + k)
Guaranteed worst case	Yes	No	No	Yes for reads	No (probabilistic)

n is the number of keys and k the number of results in a range. A balanced tree wins when you need ordered operations and updates together, and it never beats a hash table at exact lookups alone. A skip list is a layered linked list that gets the same ordered behaviour from random coin flips instead of rotations.

Edge cases

Empty tree. The first insert becomes the root with height 1 and no rotation.
One or two keys. Balance factors stay within -1 to +1, so the first rotation can only happen on the third key.
Duplicate keys. The simulation sends an equal key to the right. Library maps such as TreeMap keep one entry per key and replace its value, and a multiset allows copies. Rotations keep the in-order order either way, but decide your duplicate rule before you write the insert.
Reverse-sorted input. The mirror image of sorted input: left-left cases and right rotations. Inserting 7, 6, 5, 4, 3, 2, 1 also ends with height 3 after 4 rotations.
Delete a node with two children. Replace it with its in-order successor (or predecessor), remove that node, then walk up and rebalance.
Delete where the heavy child has factor 0. This cannot happen on insert. A single rotation fixes it, and the height of that subtree does not shrink, so the walk up can stop.
Very large inputs. The height stays about log2(n), so even a million keys need only about 20 to 30 levels of recursion.

Common mistakes

Forgetting to update heights after a rotation. Update the lower node first, then the new top, or the balance factors above will be stale.
Picking the case from z alone. You also need the balance factor of the heavy child, otherwise you cannot tell a single rotation from a double one.
Rotating at the wrong node. Rotate at the first (lowest) out-of-balance node on the way back up, not at the root.
Stopping the walk up after a delete. An insert can stop after one rebalancing, but a delete may shrink a subtree and unbalance a node higher up.
Thinking "balanced" means "perfect". The tree only needs its height to stay O(log n). Its two sides may still differ by one level.
Believing a rotation changes the order. It changes only the shape. The in-order sequence is always the same.

How to spot a balanced-tree problem

Look for these signals in a problem statement:

Items arrive and leave over time and you must keep them in sorted order.
You are asked for the next larger, previous smaller, floor or ceiling of a value, or for everything in a range.
The input may arrive already sorted, or an adversary may choose it, so you need a guaranteed O(log n) and not an average.
The statement sounds like a calendar or booking check ("does this new interval overlap an existing one?") or a running median over a sliding window.

If none of these appear, a hash table (exact lookups), a heap (only the smallest or largest) or a sorted array (read-only data) is simpler. In an interview, reach for the language's ordered map or set, such as TreeMap or std::set, and be ready to explain how it stays balanced.

How to explain balanced trees in an interview

State the problem first: "a plain BST can become a line, so search is O(n). A balanced tree keeps the height O(log n)."
State the AVL invariant: "left and right heights differ by at most 1 at every node." Then name the four cases and say that each is fixed with one or two rotations in O(1).
Say that rotations preserve the in-order order, and that insert needs at most one rebalancing, which is one or two rotations.
Be ready to trace a short insert sequence by hand, naming the case (left-left, left-right and so on) at each rotation.
Compare AVL and red-black trees: "AVL is stricter, so lookups are faster; red-black rotates less, so updates are cheaper. Standard libraries mostly use red-black trees or B-trees."

Where you meet balanced trees in real systems

You rarely write an AVL tree at work, but balanced search trees sit underneath the sorted maps, schedulers and indexes you use. Here are three of them drawn out, the first with code you can run, then more examples.

Example 1: An event timeline indexed by timestamp

A scheduling or logging service stores events keyed by timestamp. Events usually arrive in time order, which is exactly the input that turns a plain binary search tree into a straight line. A balanced tree rotates as it goes, so "find the first event after 10:30" or "list everything between 10:00 and 10:15" stays O(log n). Open the example below to see the picture and the code.

Code: AVL insert with rotationsTime O(log n)Memory O(n)

A plain tree would be a line of height 7. The AVL tree rotated four times along the way and ends perfectly balanced with height 3, with 4 at the top.

# AVL tree insert with rotations. Every node keeps its height, and the heights of its two
# subtrees may differ by at most 1.
# Time: O(log n) per insert (at most 2 rotations). Memory: O(n) for n nodes, O(log n) recursion depth.
class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1

def h(n):
    return n.h if n else 0

def fix(n):
    n.h = 1 + max(h(n.left), h(n.right))

rotations = 0

def rotate_right(z):
    global rotations
    rotations += 1
    y = z.left
    z.left, y.right = y.right, z      # y moves up, z becomes its right child
    fix(z); fix(y)
    return y

def rotate_left(z):
    global rotations
    rotations += 1
    y = z.right
    z.right, y.left = y.left, z
    fix(z); fix(y)
    return y

def insert(n, key):
    if n is None:
        return Node(key)
    if key < n.key:
        n.left = insert(n.left, key)
    else:
        n.right = insert(n.right, key)
    fix(n)
    bf = h(n.left) - h(n.right)       # balance factor
    if bf > 1:                        # left side too tall
        if h(n.left.left) < h(n.left.right):
            n.left = rotate_left(n.left)      # left-right case: straighten first
        return rotate_right(n)
    if bf < -1:                       # right side too tall
        if h(n.right.right) < h(n.right.left):
            n.right = rotate_right(n.right)   # right-left case: straighten first
        return rotate_left(n)
    return n

def preorder(n, out):
    if n:
        out.append(n.key); preorder(n.left, out); preorder(n.right, out)

root = None
for k in range(1, 8):                 # sorted input: a plain BST would become a straight line
    root = insert(root, k)
order = []
preorder(root, order)
print("height:", h(root))
print("preorder:", *order)
print("rotations:", rotations)

Each version inserts the keys 1 to 7 in order into an AVL tree, then prints the height, the keys in pre-order and the number of rotations. Every version was compiled and run, and printed height 3, pre-order 4 2 1 3 6 5 7 and 4 rotations. The Rust version uses Option<Box<Node>>, and the C++ version uses std::unique_ptr, so ownership is explicit.

Example 2: Database indexes

A relational database keeps an index on a column as a B-tree, a balanced tree where each node holds many keys and has many children. The same balancing idea applies, but a node fills one disk page, so a lookup in a table of a billion rows reads only a few pages. Range queries find the first key and then read forward in order.

Each step reads one page, picks the child whose range contains the key, and goes down. A tall, narrow tree is replaced by a short, wide one: three or four page reads can cover a very large table.

Example 3: Reading balance factors

After every insert or delete, a balanced tree walks back up the path it used and recomputes each node's balance factor (left height minus right height). The first node that reads 2 or -2 is where the rotation happens. Here 10, 20 and 30 were inserted in order, so the chain leans right.

After an insert, each node on the path gets a new balance factor (left height minus right height). The first node reading 2 or -2 is where the rotation happens.

More real-world scenarios

Scenarios 4 to 6 describe named libraries and systems. Scenarios 7 to 12 describe typical designs and are illustrative, not claims about any specific product.

4. Ordered maps in standard libraries

Java's TreeMap and TreeSet, and C++'s std::map and std::set, are typically red-black trees. They give ordered iteration, floor and ceiling lookups and range views with guaranteed O(log n) operations.

5. Linux and operating systems

The Linux kernel uses red-black trees in several places, for example to track memory areas of a process and, for a long time, the tasks of its scheduler. The kernel ships a generic red-black tree library for this.

6. Java's `HashMap` buckets

When many keys collide in one bucket of a Java HashMap, the bucket is turned from a linked list into a red-black tree once it grows past a small threshold. A flood of colliding keys then costs O(log n) per lookup instead of O(n).

7. Interval and calendar queries

A calendar that must answer "is this time free?" keeps booked intervals in a balanced tree sorted by start time, and finds the neighbours of a new booking in O(log n).

8. Order books and price ladders

Exchanges keep buy and sell orders sorted by price so the best price is always at one end. Orders arrive and are cancelled constantly, so insert and delete must be fast and ordered.

9. Leaderboards and rankings

A game that needs "the three players just above me" or "everyone between 1,000 and 2,000 points" needs data that stays sorted while scores change.

10. Memory allocators and file systems

Allocators keep free blocks sorted by size or address in a balanced tree to find the best fit quickly. Some file systems use B-tree variants for directories and extents.

11. Timers and schedulers

A server with thousands of timeouts keeps them ordered by expiry time. A balanced tree (or a heap) gives the next timeout and lets timers be cancelled in O(log n).

12. Compilers and symbol tables

Some compilers and interpreters keep symbols in ordered maps so they can list names alphabetically or find the nearest match for an error suggestion.

Language standard libraries

Most languages already ship a sorted map or set built on a balanced tree. Check how yours works before writing your own. No mainstream library uses AVL specifically.

Language	Sorted map or set	What it is under the hood	Notes
Java	`TreeMap`, `TreeSet`	Red-black tree	Has `floorKey`, `ceilingKey` and `subMap` for range queries.
C++	`std::map`, `std::set`	Usually a red-black tree	`lower_bound` and `upper_bound` for nearest-key and range queries.
C#	`SortedDictionary`, `SortedSet`	Red-black tree	`SortedSet` has `GetViewBetween` for ranges.
Rust	`BTreeMap`, `BTreeSet`	B-tree, not a binary tree	Use `range(a..b)` for range queries. Rust's `HashMap` is unordered.
Python	None built in	Third-party `sortedcontainers` (`SortedDict`, `SortedList`)	Not a tree, but gives the same ordered operations. For plain sorted lists, use the built-in `bisect` module.
Go	None built in	Third-party packages, such as `github.com/google/btree`	Go's built-in `map` is a hash map with no ordering.
JavaScript	None built in	Third-party packages	`Map` keeps insertion order, not sorted order.
Kotlin	`TreeMap`, `sortedMapOf`	Red-black tree (uses Java's)	Same operations as Java.

The takeaway from the table: the languages that ship an ordered structure use a balanced tree for it. The ones that don't expect you to pull in a package, or to keep a sorted array and use binary search.

The takeaway

Whenever a system needs ordered data that keeps changing, look for a self-balancing tree such as an AVL, red-black or B-tree. When it only needs exact-match lookups, it usually uses a hash table instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Check whether a binary tree is height-balanced (every node's subtrees differ in height by at most 1).
easy
2.
Convert a sorted array into a height-balanced BST.
easy
3.
Explain the four AVL rotation cases and draw the left-right case.
medium
4.
Why do standard libraries use red-black trees more than AVL trees?
medium
5.
Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. Name each rotation and draw the final tree.
medium
6.
How does a balanced tree answer "the smallest key at least x" and "all keys between a and b"?
medium

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Segment Tree and Fenwick Tree

Probabilistic Data Structures

Topics:TreesAvl treeRed black treeRotationsSelf balancingBinary search tree

Balanced Trees

Key takeaways

When to use a balanced tree

How a balanced tree works

Try it

Balanced tree operations: search, insert, delete and rotate

Worked example: reading and fixing an imbalance by hand

Balanced tree time complexity

Balanced trees vs other data structures

Edge cases

Common mistakes

How to spot a balanced-tree problem

How to explain balanced trees in an interview

Where you meet balanced trees in real systems

Example 1: An event timeline indexed by timestamp

Example 2: Database indexes

Example 3: Reading balance factors

More real-world scenarios

4. Ordered maps in standard libraries

5. Linux and operating systems

6. Java's HashMap buckets

7. Interval and calendar queries

8. Order books and price ladders

9. Leaderboards and rankings

10. Memory allocators and file systems

11. Timers and schedulers

12. Compilers and symbol tables

Language standard libraries

The takeaway

Interview questions

6. Java's `HashMap` buckets