頂点 \(1\) に \(1\) に書き込むものを再帰的に構成します．

\(N=1\) のときは \((1)\) です．

\(N-1\) のときの答えを \(P\) とします．\(L=P,R=P\) として，以下のように構築します．

1. 各 \(i=1,2,\ldots,2^{N-1}-1\) に対して， \(L_i\) に \(1\) を，\(R_i\) に \(2^{N-1}-1\) を加える．
2. \(R_1=2^N-1\) とする．
3. 各 \(i=2^{N-2},\ldots,2^{N-1}-1\) に対して，\(L_i\) と \(R_i\) を swap する．
4. 頂点 \(1\) に \(1\) を書き込み，頂点 \(2\) の部分木には \(L\) を，頂点 \(3\) の部分木には \(R\) を書き込む．

この書き込み方は条件を満たします．順列であることや，左右の部分木の数の総和の差が \(1\) になっていることは簡単な計算によって確かめられます．