# Finite Rooted Binary Trees

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]$.

• Could you please explain what $[T_1\leftarrow T_2]$ means, for those of us who don't have access to the book? – Tara B May 19 '12 at 7:44
• Sorry about that. first dyadic divisions of [0,1] correspond with finite rooted bianry trees. $[T_1 \leftarrow T_2]$ is the thompson function where the domain is divided according to $T_2$ and the range according to $T_1$. A dyadic division of [0,1] is constructed by dividing [0,1] into [0, 1/2] and [1/2,1] and then one picks middles of the resulting pieces in a finite number of times. – Jami May 19 '12 at 7:57
• Thanks. It would be best if you edit that information into the question itself. I'm not sure everyone would know what the Thompson function is, and you also haven't explained precisely how you obtain the diadic division of $[0,1]$ from a given rooted binary tree. Also, I don't understand the relevance of your last sentence, because you haven't used $\sim$ anywhere else. – Tara B May 19 '12 at 8:09
• @Jami You really have to define the function. – Phira May 19 '12 at 10:19

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 ;-)

• Thank you. The only thing I am confused about is this: $f_{T1 \leftarrow T2}$ composed with $f_{T2 \leftarrow T3}$ = $f_{T1 \leftarrow T3}$. Why are they in a different order then the lemma..Sorry I am really confused. – Jami May 20 '12 at 3:26
• @Jami Just permute the numbers (e.g. swap 1 and 3) and you will get $f_{T_3\gets T_2}\circ f_{T_2 \gets T_1} = f_{T_3 \gets T_1}$. After all, those are just labels. – dtldarek May 20 '12 at 8:52