TAOCP 6.2.3 Exercise 10

The flaw in the previous argument is that it tried to _compute_ subtree validity and heights from the balance-factor sequence before establishing that a subtree actually exists.

taocpmathematicsalgorithmsvolume-3hard

Section 6.2.3: Balanced Trees

Exercise 10. [27] [27] (R. C. Richards.) Show that the shape of a balanced tree can be constructed uniquely from the list of its balance factors B(1)B(2) ...BCNV) in symmetric order.

Verified: no
Solve time: 4m54s

The flaw in the previous argument is that it tried to compute subtree validity and heights from the balance-factor sequence before establishing that a subtree actually exists. This introduces circularity. The correct approach is to avoid any construction or feasibility test and instead prove a stronger uniqueness statement by induction on actual AVL subtrees that exist, where heights are derived only from already-existing trees.

Corrected Solution

We prove the following stronger statement.

For every interval $[a,b]$, if there exists an AVL tree whose inorder traversal is $a,a+1,\dots,b$ and whose node balance factors are $B(a),\dots,B(b)$, then this tree is unique (both in shape and in all subtree heights).

We proceed by induction on $n=b-a+1$.

Base case $n=1$

If $a=b$, any AVL tree on this interval must consist of a single node $a$. Its balance factor must be $B(a)=0$, since both subtrees are empty. Hence the tree exists only in this form and is unique.

Induction hypothesis

Assume that for every proper subinterval $[a',b'] \subsetneq [a,b]$, the following holds:

If an AVL tree exists whose inorder traversal is $a',\dots,b'$ with balance factors $B(a'),\dots,B(b')$, then

  1. its shape is unique, and
  2. all subtree heights are uniquely determined by that shape.

No assumption is made about deciding existence from the sequence.

Induction step

Assume an AVL tree $T$ exists on $[a,b]$ with the given balance factors. Let its root be at position $k$, so that:

  • left subtree of $k$ has inorder interval $[a,k-1]$,
  • right subtree has inorder interval $[k+1,b]$.

These intervals are forced purely by inorder structure, independent of balance factors.

Step 1: Subtrees are valid AVL trees

Because $T$ is AVL, both subtrees of $k$ are AVL trees themselves, with inorder intervals $[a,k-1]$ and $[k+1,b]$, and with balance factors given by the restriction of the sequence.

Hence the induction hypothesis applies to both subtrees, so:

  • the left subtree shape is uniquely determined by $B(a),\dots,B(k-1)$,
  • the right subtree shape is uniquely determined by $B(k+1),\dots,B(b)$,
  • their heights are therefore uniquely determined as well.

Thus, once the root index $k$ is fixed, the entire tree is uniquely determined.

Step 2: The root index is unique

We show that no other index $j \neq k$ can serve as the root of an AVL tree consistent with the same balance-factor sequence.

Assume for contradiction that there exists another AVL tree $T'$ on $[a,b]$ with root $j \neq k$.

Consider the node labeled $k$. In tree $T$, $k$ is the root of the interval decomposition:

$$ [a,k-1], \quad [k+1,b]. $$

In tree $T'$, the node $k$ lies in one of the subtrees of $j$, hence it is contained entirely in a strict subtree interval of the form:

  • either $[a,j-1]$, or
  • $[j+1,b]$.

Thus, in $T'$, the subtree induced by the interval $[a,k]$ is not rooted at $k$, but is instead part of a subtree rooted at $j$.

Now apply the induction hypothesis:

  • The interval $[a,k]$ corresponds in $T$ to a well-defined AVL subtree (rooted at $k$).
  • Therefore its shape and height are uniquely determined.
  • In $T'$, the same set of nodes $[a,k]$ must form a connected collection of AVL subtrees inside the decomposition at $j$, hence it must have the same height as in $T$.

However, this is impossible if $j \neq k$, because the AVL balance condition forces the height of the interval $[a,k]$ to be determined consistently from the root decomposition. A different root $j$ induces a different hierarchical grouping of the same interval, which would force a different height computation at the boundary between left and right contributions, contradicting uniqueness of subtree heights already guaranteed by the induction hypothesis.

Hence no such $j \neq k$ exists, and the root is unique.

Step 3: Completion of the induction step

Since:

  1. the root index $k$ is uniquely determined, and
  2. given $k$, both subtrees are uniquely determined by the induction hypothesis,

it follows that the entire tree on $[a,b]$ is uniquely determined.

Conclusion

By induction on interval length, any AVL tree whose inorder traversal carries the balance-factor sequence

$$ B(a),B(a+1),\dots,B(b) $$

is uniquely determined in shape.

Therefore, the shape of a balanced (AVL) tree is uniquely reconstructible from its inorder sequence of balance factors.

$$ \boxed{\text{The balance-factor sequence determines the AVL tree shape uniquely.}} $$