Introduction

An AVL tree is never allowed to become wildly skewed, but some valid AVL trees are still more lopsided than others. A maximally unbalanced AVL tree means a legal AVL tree of a given height that uses the minimum number of nodes, which makes the shape as stretched as the AVL rule allows.

The Shape of the Most Skewed Valid AVL Tree

For a tree to be AVL-valid, every node must have left and right subtree heights differing by at most one. If you want the most lopsided shape at height h, one subtree should have height h - 1 and the other should have height h - 2.

That leads to the classic recurrence for the minimum number of nodes in an AVL tree:

N(h) = 1 + N(h - 1) + N(h - 2)

with base cases:

• 'N(0) = 1'
• 'N(1) = 2'

This is the key insight. A maximally unbalanced AVL tree is built by recursively attaching:

• a minimal AVL tree of height h - 1
• a minimal AVL tree of height h - 2

The tree is still balanced, but only barely.

Recursive Construction

The easiest way to generate the shape is to construct only the tree heights first, then assign keys in sorted order so the result is also a valid binary search tree.

Here is a Python example that builds a minimal-node AVL tree for a requested height:

1from dataclasses import dataclass
2
3
4@dataclass
5class Node:
6    key: int
7    left: "Node | None" = None
8    right: "Node | None" = None
9
10
11def build_min_avl(height: int, next_key: list[int]) -> Node | None:
12    if height < 0:
13        return None
14
15    left = build_min_avl(height - 1, next_key)
16    root = Node(next_key[0])
17    next_key[0] += 1
18    right = build_min_avl(height - 2, next_key)
19
20    root.left = left
21    root.right = right
22    return root
23
24
25def inorder(node: Node | None) -> list[int]:
26    if node is None:
27        return []
28    return inorder(node.left) + [node.key] + inorder(node.right)
29
30
31tree = build_min_avl(4, [1])
32print(inorder(tree))

This code gives the left subtree the larger height. If you want the mirrored version, swap the recursive calls for the left and right child.

Why This Produces Maximum AVL Imbalance

Suppose the root has height h. Any AVL-valid pair of subtree heights must be one of the following:

• 'h - 1 and h - 1'
• 'h - 1 and h - 2'

The pair h - 1 and h - 2 is the most skewed legal choice. If you also want the fewest nodes for that height, each subtree must itself be a minimal AVL tree. That is why the recurrence works at every level, not just the root.

You can also compute the minimal node counts directly:

1def min_nodes(height: int) -> int:
2    if height == 0:
3        return 1
4    if height == 1:
5        return 2
6    a, b = 1, 2
7    for _ in range(2, height + 1):
8        a, b = b, 1 + b + a
9    return b
10
11
12for h in range(6):
13    print(h, min_nodes(h))

Typical output is:

10 1
21 2
32 4
43 7
54 12
65 20

Those counts grow in a Fibonacci-like way because each height depends on the previous two heights.

Assigning Keys Correctly

If you only care about shape, you can store placeholder values. If you need a true AVL search tree, assign keys in in-order sequence. The earlier Python example does that by:

• building the left subtree
• placing the current key at the root
• building the right subtree

That guarantees:

• every left key is smaller than the root key
• every right key is larger than the root key

So the result is both an AVL tree and a binary search tree.

Common Pitfalls

One common mistake is to keep extending only one side of the tree. That quickly breaks the AVL rule because subtree heights start differing by more than one. A valid maximally unbalanced AVL tree is not arbitrary skew; it is carefully skewed.

Another mistake is using the wrong base cases. If you define height differently, your recurrence can still be right in spirit but wrong in counts. Be consistent about whether an empty tree has height -1 or 0.

A third issue is inserting sequential keys into a normal AVL implementation and expecting the final shape to match the minimal-node construction exactly. AVL insertions preserve balance, but the resulting shape depends on rotation history. If you want the specific maximally unbalanced form, construct it directly.

Finally, people often confuse "maximally unbalanced AVL" with "worst-case AVL after arbitrary insertions." The minimal-node tree is the theoretical extreme for a chosen height, not the only possible sparse AVL tree.

Summary

• A maximally unbalanced AVL tree is the minimal-node AVL tree for a given height.
• Its subtree heights are recursively h - 1 and h - 2.
• The node-count recurrence is N(h) = 1 + N(h - 1) + N(h - 2).
• Build the shape recursively, then assign keys in-order if you need a search tree.
• Do not confuse a legal AVL extreme with an arbitrarily skewed binary tree.