<p>As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function</p>

<p>$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.</p>

<p>On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have <em>rational</em> generating functions.</p>

<p>Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.</p>

<p>(Note that the generating function of arbitrary binary trees is not rational, either.)</p>

CC BY-SA 3.0
2011-07-11T06:47:56.983Z
Note that there might be some subtleties here as the number of trees with $n$ leaves need not be the number of encodings of length $n$, even for a valid encoding (due to encoding inner nodes, "management" symbols, ...). As rational functions are stable against coefficient shifts, constant factors and the like, I figure the implication remains valid. Also, the rational function you get for trees with $n$ nodes is not rational, either.
Raphael
CC BY-SA 3.0
2011-07-11T07:24:49.197Z
Peter used the Catalan numbers to demonstrate a regular encoding of full binary trees. Whether the Catalan numbers are regular is no more relevant than whether he used a programming language with matched parentheses to demonstrate how to produce the encoding.
Dave
CC BY-SA 3.0
2011-07-11T08:17:29.310Z
This would suggest that there is no regular language for the **number** of binary trees, but does this preclude a regular language for each individual binary tree?
templatetypedef
CC BY-SA 3.0
2011-07-11T15:48:48.003Z
I think you both misunderstand. I prove that there is no regular language that has as many words of length $n$ as there are (full) binary trees with $n+1$ leaves (and other graph classes/ways of counting). Together with my first comment, I think this proves that there is no *suitable* regular, bijective encoding of binary trees. Of course, there *are* bijections between any infinite regular language and the set of all (full) trees as both sets are countable, but wether the resulting bijection is reasonable or even computable remains to be seen.
Raphael
CC BY-SA 3.0
2011-07-11T15:49:55.223Z
By "suitable", I mean something like length blowup by management symbols by a constant factor or the like. Arbitrary bijections might do very weird things.
Raphael
CC BY-SA 3.0
2011-07-11T06:28:21.100Z
2011-07-11T06:34:35.777Z
2011-07-11T06:34:35.777Z
Raphael
<p>Here is what I think is a legitimate encoding of binary trees as strings in $\Sigma^*$ (which is a regular language). Consider a breadth-first enumeration of the nodes in the infinite binary tree. Each node is labeled as a letter or as NIL. The nodes with letters belong to the tree, those labeled NIL do not. The caveat is that a subword of NIL's longer than the prefix preceding it terminates the tree -- meaning that this encoding is not a bijection.
For example, the string abc00de encodes the 5-node tree</p>

<blockquote>
<pre><code>    a
   / \
  b   c
 / \ / \
0  0 d e
</code></pre>
</blockquote>

<p>but the sequence a00bcde encodes the 1-node tree</p>

<blockquote>
<pre><code>    a
   / \
  0   0
</code></pre>
</blockquote>

<p>(because 0/NIL cannot have children). Is this what you had in mind?</p>

CC BY-SA 3.0
2011-07-10T16:42:19.193Z
In my encoding, every string in $\Sigma^*$ encodes some binary tree -- and $\Sigma^*$ is a regular language.
Aryeh
CC BY-SA 3.0
2011-07-11T06:34:23.530Z
Please give a formal definition of your encoding.
Raphael
CC BY-SA 3.0
2011-07-11T07:08:03.843Z
Note how $a0b$ (and infinitely many more examples) does not encode a *full* binary tree. I do think, however, that you can interpret any string over $\Sigma \cup \{0\}$ as an unrestricted binary tree.
Raphael
CC BY-SA 3.0
2011-07-11T10:52:15.210Z
indeed -- and I did not think that templatetypedef wanted full binary trees. I think I can prove that there can be no regular encoding of full binary trees; let me know if there is sufficient interest for me to go through the trouble.
Aryeh
CC BY-SA 3.0
2011-07-11T15:52:57.093Z
The OP's grammar explicitly models full trees, so I figure he/she wants those. Salvaging your idea (which still has to be formalised, mind!), you can obtain a regular (non-bijective) encoding by using $(\Sigma^2 | 00)^*$, I guess.
Raphael
CC BY-SA 3.0
2011-07-10T13:42:46.493Z
2011-07-10T13:42:46.493Z
Aryeh
<p>There are many ways of representing binary trees as strings.  For example, I could encode a tree as either nil or a pair of trees, such as</p>

<pre><code>(nil, ((nil, nil), nil))
</code></pre>

<p>This representation has a simple CFG:</p>

<pre><code>S -&gt; nil
S -&gt; (S, S)
</code></pre>

<p>My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language.  I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.</p>

<p>Does such a representation exist?</p>

CC BY-SA 3.0
2011-07-10T14:22:56.027Z
You have to be careful how to formulate this question. For example, there is a polynomial-time computable one-to-one mapping of all binary trees to the positive integers, and the positive integers (in binary) are certainly a regular language.
Peter Shor 
CC BY-SA 3.0
2011-07-10T17:27:39.217Z
@Peter Shor- I apologize if I'm missing something obvious, but what is this mapping?  That's pretty much the answer to the question I'm asking.  If this is a well-known result, is there a particular reference I should look up for more information?
templatetypedef
CC BY-SA 3.0
2011-07-10T17:37:07.483Z
If you're talking about complete binary trees, so each node has either 0 or 2 children, then the number of trees on $n$ nodes is given by the [Catalan numbers](http://en.wikipedia.org/wiki/Catalan_number), and this fact (with a reasonable amount of extra work) is enough to construct a mapping in polynomial time. I don't have time to go into the details right now. It's probably written up somewhere.
Peter Shor 
CC BY-SA 3.0
2011-07-10T18:12:00.147Z
If you convert a tree into series of opening and closing brackets e.g. (()(())) replace ( with 1 and ) with 0. Will this work?
Pratik Deoghare
CC BY-SA 3.0
2011-07-10T18:21:44.363Z
@MachineCharmer- Unfortunately no, since that language is not regular (though it is context-free).
templatetypedef
CC BY-SA 3.0
2011-07-10T19:02:20.117Z
Succinct encodings might be regular. Not sure though. "One simple representation  is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf." [wiki](http://en.wikipedia.org/wiki/Binary_tree#Succinct_encodings)
Pratik Deoghare
CC BY-SA 3.0
2011-07-10T21:36:21.907Z
You can produce a regular language from any unique encoding of anything to a string. Simply take the lexicographic ordering of the encodings, and let $i$ represent the $i$th encoding in the ordering. This is what Peter meant when he said to be careful about the formulation. With trees, you can even do this in poly time.
Dave
CC BY-SA 3.0
2011-07-11T06:15:32.720Z
@Peter Shor: There are non-complete trees which have the property that any node has either zero or two children, e.g. $N(N,N(N, N))$. According to Wikipedia, the property you mean is *full*. (Sorry for nitpicking, but it is of import if we are counting trees.)
Raphael
CC BY-SA 3.0
2011-07-11T10:33:09.677Z
@Raphael: Indeed, I should have said *full*.
Peter Shor 
<ds.data-structures><fl.formal-languages>
Encoding of binary trees as a regular language?
templatetypedef
# Encoding of binary trees as a regular language?

(Asked by: username_0 on 2011-07-10)

There are many ways of representing binary trees as strings.  For example, I could encode a tree as either nil or a pair of trees, such as
(nil, ((nil, nil), nil))

This representation has a simple CFG:
S -> nil
S -> (S, S)

My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language.  I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.
Does such a representation exist?

**Tags:** ds.data-structures, fl.formal-languages
> **Comments:**
> **username_1**: You have to be careful how to formulate this question. For example, there is a polynomial-time computable one-to-one mapping of all binary trees to the positive integers, and the positive integers (in binary) are certainly a regular language.  
> **username_0**: @Peter Shor- I apologize if I'm missing something obvious, but what is this mapping?  That's pretty much the answer to the question I'm asking.  If this is a well-known result, is there a particular reference I should look up for more information?  
> **username_1**: If you're talking about complete binary trees, so each node has either 0 or 2 children, then the number of trees on $n$ nodes is given by the [Catalan numbers](http://en.wikipedia.org/wiki/Catalan_number), and this fact (with a reasonable amount of extra work) is enough to construct a mapping in polynomial time. I don't have time to go into the details right now. It's probably written up somewhere.  
> **username_2**: If you convert a tree into series of opening and closing brackets e.g. (()(())) replace ( with 1 and ) with 0. Will this work?  
> **username_0**: @MachineCharmer- Unfortunately no, since that language is not regular (though it is context-free).  
> **username_2**: Succinct encodings might be regular. Not sure though. "One simple representation  is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf." [wiki](http://en.wikipedia.org/wiki/Binary_tree#Succinct_encodings)  
> **username_3**: You can produce a regular language from any unique encoding of anything to a string. Simply take the lexicographic ordering of the encodings, and let $i$ represent the $i$th encoding in the ordering. This is what Peter meant when he said to be careful about the formulation. With trees, you can even do this in poly time.  
> **username_4**: @Peter Shor: There are non-complete trees which have the property that any node has either zero or two children, e.g. $N(N,N(N, N))$. According to Wikipedia, the property you mean is *full*. (Sorry for nitpicking, but it is of import if we are counting trees.)  
> **username_1**: @Raphael: Indeed, I should have said *full*.  

---

## 2 answers

### Answer by username_4 on 2011-07-11. Score: 10

As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C\_n$. It is known that the Catalan numbers have generating function

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.

On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have *rational* generating functions.

Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.

(Note that the generating function of arbitrary binary trees is not rational, either.)

> **Comments:**
> **username_4**: Note that there might be some subtleties here as the number of trees with $n$ leaves need not be the number of encodings of length $n$, even for a valid encoding (due to encoding inner nodes, "management" symbols, ...). As rational functions are stable against coefficient shifts, constant factors and the like, I figure the implication remains valid. Also, the rational function you get for trees with $n$ nodes is not rational, either.  
> **username_3**: Peter used the Catalan numbers to demonstrate a regular encoding of full binary trees. Whether the Catalan numbers are regular is no more relevant than whether he used a programming language with matched parentheses to demonstrate how to produce the encoding.  
> **username_0**: This would suggest that there is no regular language for the **number** of binary trees, but does this preclude a regular language for each individual binary tree?  
> **username_4**: I think you both misunderstand. I prove that there is no regular language that has as many words of length $n$ as there are (full) binary trees with $n+1$ leaves (and other graph classes/ways of counting). Together with my first comment, I think this proves that there is no *suitable* regular, bijective encoding of binary trees. Of course, there *are* bijections between any infinite regular language and the set of all (full) trees as both sets are countable, but wether the resulting bijection is reasonable or even computable remains to be seen.  
> **username_4**: By "suitable", I mean something like length blowup by management symbols by a constant factor or the like. Arbitrary bijections might do very weird things.  

---

### Answer by username_5 on 2011-07-10. Score: 3

Here is what I think is a legitimate encoding of binary trees as strings in $\Sigma^*$ (which is a regular language). Consider a breadth-first enumeration of the nodes in the infinite binary tree. Each node is labeled as a letter or as NIL. The nodes with letters belong to the tree, those labeled NIL do not. The caveat is that a subword of NIL's longer than the prefix preceding it terminates the tree -- meaning that this encoding is not a bijection.
For example, the string abc00de encodes the 5-node tree

    a
   / \
  b   c
 / \ / \
0  0 d e


but the sequence a00bcde encodes the 1-node tree

    a
   / \
  0   0


(because 0/NIL cannot have children). Is this what you had in mind?

> **Comments:**
> **username_5**: In my encoding, every string in $\Sigma^*$ encodes some binary tree -- and $\Sigma^*$ is a regular language.  
> **username_4**: Please give a formal definition of your encoding.  
> **username_4**: Note how $a0b$ (and infinitely many more examples) does not encode a *full* binary tree. I do think, however, that you can interpret any string over $\Sigma \cup \{0\}$ as an unrestricted binary tree.  
> **username_5**: indeed -- and I did not think that templatetypedef wanted full binary trees. I think I can prove that there can be no regular encoding of full binary trees; let me know if there is sufficient interest for me to go through the trouble.  
> **username_4**: The OP's grammar explicitly models full trees, so I figure he/she wants those. Salvaging your idea (which still has to be formalised, mind!), you can obtain a regular (non-bijective) encoding by using $(\Sigma^2 | 00)^*$, I guess.  

---

