TAOCP 2.3.4.6 Exercise 1
Let the sides of the convex $(n+2)$-gon be distinct and let one of them be designated as the root side $r$.
Section 2.3.4.6: History and Bibliography
Exercise 1. [**] [21] Find a simple one-to-one correspondence between binary trees with $n$ nodes and dissections of an $(n+2)$-sided convex polygon into $n$ triangles, assuming that the sides of the polygon are distinct.
Verified: yes
Solve time: 2m39s
Let the sides of the convex $(n+2)$-gon be distinct and let one of them be designated as the root side $r$. Since the sides are distinct, every side can be referred to unambiguously throughout the construction.
We define a correspondence between triangulations of the polygon and binary trees with $n$ nodes.
From a triangulation to a binary tree
Let $P$ be a triangulated $(n+2)$-gon.
The root side $r$ belongs to a unique triangle $T$. Associate $T$ with the root node of a binary tree.
Let the third vertex of $T$ be $v$. The two sides of $T$ different from $r$ cut $P$ into two smaller polygons, one on each side of $v$. Some of these polygons may degenerate to a single edge.
To distinguish left from right, orient the boundary of $P$ counterclockwise. Traversing the boundary from one endpoint of $r$ to the other, one of the resulting subpolygons lies on the left side of $T$ and the other on the right. Define:
- the left subtree to be the tree corresponding to the left subpolygon;
- the right subtree to be the tree corresponding to the right subpolygon.
If a subpolygon degenerates to a single edge, the corresponding subtree is empty.
Apply the same procedure recursively to each nondegenerate subpolygon, using as its root side the side of $T$ that bounds it.
Since every triangle of the triangulation is encountered exactly once, the resulting binary tree has exactly $n$ nodes.
From a binary tree to a triangulation
Conversely, let $B$ be a binary tree with $n$ nodes.
We construct a triangulation recursively.
If $B$ is empty, the corresponding polygon is a single side.
Suppose $B$ has root $x$, left subtree $L$, and right subtree $R$. Let
$$ |L|=a,\qquad |R|=b. $$
Then
$$ a+b+1=n. $$
By induction, $L$ corresponds to a triangulated $(a+2)$-gon and $R$ corresponds to a triangulated $(b+2)$-gon.
Consider an $(n+2)$-gon with root side $r$. Draw a triangle $T$ having $r$ as one side and chosen so that the two subpolygons cut off by $T$ have respectively
$$ (a+2)\ \text{and}\ (b+2) $$
sides. Such a triangle is uniquely determined because the polygon sides are distinct and occur in a fixed cyclic order.
Insert recursively the triangulation corresponding to $L$ in the left subpolygon and the triangulation corresponding to $R$ in the right subpolygon.
The resulting figure is a triangulation of the entire $(n+2)$-gon.
Proof that the correspondence is a bijection
We prove by induction on $n$.
For $n=0$, a single side corresponds to the empty tree. The correspondence is trivial.
Assume the statement true for all smaller values.
Given a triangulation, the triangle incident with the root side $r$ is uniquely determined. It uniquely determines the two subpolygons and hence, by induction, the left and right subtrees. Therefore the associated binary tree is uniquely determined.
Conversely, given a binary tree, the sizes $a$ and $b$ of the left and right subtrees uniquely determine the root triangle. By induction, the triangulations placed in the two subpolygons are uniquely determined. Hence the resulting triangulation is unique.
Applying the first construction and then the second clearly reproduces the original triangulation, because the root triangle and both recursive subproblems are recovered exactly. Similarly, applying the second construction and then the first reproduces the original binary tree.
Therefore the two constructions are inverse to one another. Hence there is a one-to-one correspondence between binary trees with $n$ nodes and triangulations of a convex $(n+2)$-gon into $n$ triangles. ∎