TAOCP 2.3.1 Exercise 14
In the representation (2), each node contains exactly two links, `LLINK` and `RLINK`.
Section 2.3.1: Traversing Binary Trees
Exercise 14. [20] Show that if a binary tree with n nodes is represented as in (2), the total number of \Lambda links in the representation can be expressed as a simple function of n; this quantity does not depend on the shape of the tree.
Verified: no
Solve time: 27s
Solution
In the representation (2), each node contains exactly two links, LLINK and RLINK. Therefore a binary tree with $n$ nodes contains exactly
$$ 2n $$
links in all.
Among these links, some point to other nodes of the tree and the remainder are equal to $\Lambda$. Since every node except the root has exactly one parent, each nonroot node is the target of exactly one nonnull link. Conversely, every nonnull link points to a unique child node. Hence the number of nonnull links is exactly the number of nonroot nodes, namely
$$ n - 1. $$
The total number of $\Lambda$ links is therefore
$$ 2n - (n - 1) = n + 1. $$
This quantity depends only on $n$, since the argument uses only the facts that each node has two links and that a tree with $n$ nodes has exactly $n - 1$ parent-child connections.
Thus the total number of $\Lambda$ links in any binary tree with $n$ nodes is
$$ \boxed{n+1}. $$