Finite Rooted Binary Trees

Question

I am new to learning about finite rooted binary trees. This lemma below is from John Meiers book: Groups, Graphs and Trees. There is no aval proof in the book. I was just wondering is I could catch a few pointers on how I could solve this. Let $T_1$, $T_2$, and $T_3$ be finite rooted binary trees with the same number of leaves. Then $[T_3 \leftarrow T_2][T_2 \leftarrow T_1] = [T_3 \leftarrow T_1]$ and $[T_2 \leftarrow T_1]^{-1} = [T_1 \leftarrow T_2]$.

Answer 1

I am not sure if what I describe is exactly what you want, but I think it is closely related and thus might just constitute a proof when you translate it to your vocabulary.

Imagine a function $f_{T_1\to T_2} : [0,1] \to [0,1]$ given by two binary trees with the same number of leaves (say $M$) in the following way:

• mark left branch with $0$ (zero) and the right one with $1$ (one),
• you can assign to each leaf the path from root to it, which would give you a binary prefix (or a rational number in base two),
• number the leaves from left to right (this constitutes a bijection $p_T$ from prefixes to $\{1, 2, \ldots, M\}$ for each tree),
• compose the two bijections into a bijection from set of prefixes of $T_1$ to set of prefixes of $T_2$: $P = p_{T_2}^{-1}\circ p_{T_1}$,
• $f_{T_1 \to T_2}(x)$ is an extension of $P$ (each prefix is a rational number) to $[0,1]$ that just substitutes the prefixes for all the numbers (possibly changing the length of binary expansion from some rationals) and leaves the tail untouched. There are some subtleties here, e.g. does $0.0111\ldots$ has prefix $0111\ldots$ or $1000\ldots$, but I won't cover that here.

If $X$ would be a random variable $X : \Omega \to [0,1]$ then $f \circ X$ would be a random variable with different distribution, manipulating the trees it might be possible to achieve a distribution that is almost uniform. If we were to interpret $X$ as input data, then $f \circ X$ could be interpreted as a compressed output and the whole setting would be exactly the Huffman coding (e.g. if the number of symbols is of the form $2^k$ then take $T_1$ to be the Huffman tree and full binary tree of height $k$ as $T_2$).

To see that $f_{T_2 \to T_1} \circ f_{T_3 \to T_2} = f_{T_3 \to T_1}$ or with reversed arrows $f_{T_1 \gets T_2} \circ f_{T_2 \gets T_3} = f_{T_1 \gets T_3}$, just consider the definition and focus on the part where we pick the leaf number. Every time we substitute a prefix only the leaf number matters. To be more precise $f_{T_2 \to T_1} \circ f_{T_3 \to T_2}$ is an extension of $(p_{T_1}^{-1}\circ p_{T_2})\circ(p_{T_2}^{-1}\circ p_{T_3}) = p_{T_1}^{-1}\circ p_{T_3}$, but that is precisely the bijection that $f_{T_3\to T_1}$ is extended from.

To see $f_{T_1 \to T_2} = f_{T_2 \to T_1}^{-1}$, observe that for any tree $T$ the function $f_{T \to T}$ is just an identity (every prefix being substituted for itself) and thus the equality follows from the following (please note, that each $f$ is a bijection): $f_{T_1 \to T_2} \circ f_{T_2 \to T_1} = f_{T_2 \to T_2} = id = f_{T_1 \to T_1} = f_{T_2 \to T_1} \circ f_{T_1 \to T_2}$.

Hope that helps, even if just a bit ;-)