TAOCP 4.6.3 Exercise 5
Maintain, for each integer $j$ already present in the tree, two links: LINK0[$j$], pointing to the predecessor of $j$ on the unique path from the root; and LINK1[$j$], pointing to the next node on the...
Section 4.6.3: Evaluation of Powers
Exercise 5. ▶ [**] [24] Figure 14 shows the first eight levels of the "power tree." The $(k+1)$st level of this tree is defined as follows, assuming that the first $k$ levels have been constructed: Take each node $n$ of the $k$th level, from left to right in turn, and attach below it the nodes
$$n+1,\ n+a_1,\ n+a_2,\ \ldots,\ n+a_{k-1} = 2n$$
(in this order), where $1, a_1, a_2, \ldots, a_{k-1}$ is the path from the root of the tree to $n$; but discard any node that duplicates a number that has already appeared in the tree.
Design an efficient algorithm that constructs the first $r+1$ levels of the power tree. [Hint: Make use of two sets of variables LINK0[$j$], LINK1[$j$] for $0 \le j \le 2^r$; these point upwards and to the right, respectively, if $j$ is a number in the tree.]
Verified: yes
Solve time: 1m23s
Maintain, for each integer $j$ already present in the tree, two links: LINK0[$j$], pointing to the predecessor of $j$ on the unique path from the root; and LINK1[$j$], pointing to the next node on the same level. Also maintain FIRST[$k$] and LAST[$k$], the leftmost and rightmost nodes on level $k$. The path from the root to a node $n$ can then be recovered by following LINK0 repeatedly from $n$ back to $1$.
Suppose that levels $0$ through $k$ have already been constructed. To construct level $k+1$, scan the nodes $n$ of level $k$ from left to right by following LINK1. For each such $n$, recover the path
$$ 1,a_1,a_2,\ldots,a_{k-1},n $$
by tracing LINK0 upward and storing the values temporarily in reverse order. Then generate the candidates
$$ n+1,\ n+a_1,\ n+a_2,\ \ldots,\ n+a_{k-1},\ 2n $$
in this order. Whenever a candidate $m$ has not yet appeared in the tree, insert it at the right end of level $k+1$, set LINK0[$m$] to $n$, set LINK1[LAST[$k+1$]] $\leftarrow m$, and update LAST[$k+1$] $\leftarrow m$. A boolean table PRESENT[$j$] determines in constant time whether $j$ has already appeared, so duplicate nodes are discarded immediately. Since each node is generated once, and since the path to each node has length equal to its level, the total running time for constructing the first $r+1$ levels is proportional to the total number of edges traversed while recovering paths, namely
$$ \sum_{k=0}^{r} k2^{k-1} = O(r2^r). $$
The storage requirement is $O(2^r)$.