Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the numbers from $0$ to $n-1$, each occurring exactly once, the root having label zero, and so that the label of a vertex is always equal to the label of its parent plus some power of two?
Let $G$ be the oriented graph whose vertices are the integers between $0$ and $n-1$, with an edge pointing from $i$ to $j$ whenever $j-i$ is a power of two. Is it true that $G$ is "universal" for spanning binary trees, in the sense that every binary tree $T$ on $n$ nodes, oriented away from its root, is a subgraph of $G$?
(This question was asked to me, in slightly different terms, by a bioinformatician friend. At first I didn't believe it because it seems so unreasonable, but experimental data suggests that it might be true, and I have no idea why.)
I emphasize that what makes the question difficult is that the labeling has to be bijective (or, in the second formulation, $T$ is a spanning tree for $G$).
The closest I could find in the literature is the paper "On Universal Graphs for Spanning Trees" by Chung & Graham, J. London Math. Soc. 27 (1983) 203–211, mentioned in an answer to this related question, but I don't see how to apply it or adapt its technique to this particular graph $G$. The only thing I can see is that, at least, $G$ has a sensible number of edges (viz. of the order of $n\log n$).