2
$\begingroup$

The question is about finding the inverse to the problem of generating the $n^{th}$ binary tree with N labelled leaves (Generating the $n^{th}$ full binary tree over $N$ labelled leaves).

Let's say if $N = 4$, the possible set of trees are

1: (((1, 2), 3), 4)
2: (1, ((2, 3), 4))
3: ((1, (2, 3)), 4)
4: (1, (2, (3, 4)))
5: ((1, 2), (3, 4))

If I choose a specific tree from this set, let's say $(1, ((2, 3), 4))$, is there an algorithm that gives me back the value 2? The Catalan range for the problem is 1 to 5 and the unique number corresponding to the given tree is 2.

What do I mean by Catalan Range?

If there are N leaf nodes, the maximum possible binary trees is $C(N-1)$. For a given $n$, its $C(n)$ is the $n^{th}$ Catalan number. We can uniquely identify all the individual binary trees if we assign them a number from $1$ to $C(N-1)$ in order. I'm referring to this range of numbers from $1$ to $C(N-1)$ as the Catalan Range.

What scheme am I using to order the trees from $1$ to $C(N-1)$?

I don't really mind the scheme used to order the trees as long as all the trees can be uniquely identified within that scheme. For example,

$1$: The tree having just one node in the left sub tree and $N-1$ nodes in the right sub tree.
$2$: The tree still having just one node in the left sub tree and with a slightly different right sub tree now.
.
.
$C(N-1)$: The tree having $N-1$ nodes in the left sub tree and one node in the right sub tree.

For the sake of making it easier to discuss the answer, we could follow the scheme as decided by the first answer in this page.

$\endgroup$
7
  • $\begingroup$ Could you give a reference to what you call the "Catalan space" ? $\endgroup$
    – Jean Marie
    Jun 17 '20 at 7:16
  • $\begingroup$ @JeanMarie, I have explained it in the description, I'll give it another shot here. If there are N nodes, the maximum possible binary trees is C(N). C(N) is the Nth Catalan number. We can uniquely identify all the individual binary trees if we assign them a number from 1 to C(N) in order. I'm referring to this range of numbers from 1 to C(N) as the "Catalan Space". $\endgroup$
    – Ganesh
    Jun 17 '20 at 7:24
  • $\begingroup$ Which order are you using to get 1, 2, 3, 4, 5? $\endgroup$
    – J.-E. Pin
    Jun 17 '20 at 7:24
  • $\begingroup$ @J.-E.Pin Yes, that's a good question. I don't really mind the scheme used to order the trees as long as they can be uniquely identified within that scheme. For example, I could start by assigning 1 to the tree having just one node in the left sub tree and N-1 nodes in the right sub tree. 2 can be assigned to the tree with two nodes in the left sub tree and N-2 nodes in the right and so on... $\endgroup$
    – Ganesh
    Jun 17 '20 at 7:33
  • $\begingroup$ Thanks for the explanation. I have been misled by the word "space" which tends to refer to an underlying structure (algebraic, geometric, topological...). IMHO, "Catalan range" would be a more adapted word. $\endgroup$
    – Jean Marie
    Jun 17 '20 at 9:51
1
$\begingroup$

Let $f$ be the function mapping full binary trees to integers; I'll use the convention that binary trees with $n$ leaves will map to the range $\{0, 1, \dots, C_{n-1}-1\}$ because that's easier to work with in the recursion. You can add $1$ later.

If we have a binary tree $T$, let $L$ be the "left" subtree: the subtree with leaves $1, 2, \dots, k$ for some $k$. Let $R$ be the "right" subtree: the subtree with leaves $k+1, k+2, \dots, n$. We will find $f(T)$ in terms of $f(L)$, $f(R)$, and $k$ where for the purposes of finding $f(R)$ we relabel $R$ to have leave $1, 2, \dots, n-k$.

Our trees are labeled in increasing order of $k$. So before this tree, we have $$ C_0 C_{n-2} + C_1 C_{n-3} + \dots + C_{k-2} C_{n-k} $$ trees whose left subtree has $1, 2, \dots, k-1$ leaves respectively.

Next, before this particular left subtree $L$, there are $f(L)$ previous left subtrees on $k$ leaves; for each one of them, there are $C_{n-k-1}$ right subtrees. All $f(L) C_{n-k-1}$ of the combined $n$-leaf trees go before $T$.

Finally, there are $f(R)$ trees with the same left subtree, but with a right subtree preceding $R$; these also go before $T$.

Altogether, we get the recursion $$ f(T) = \sum_{i=1}^{k-1} C_{i-1} C_{n-i-1} + f(L) C_{n-k-1} + f(R). $$ The base of the recursion sets $f(T) = 0$ when $T$ has just one or two leaves, in which case there's only one possible tree. (Actually, we only need the one-leaf case as our base case.)

$\endgroup$
3
  • $\begingroup$ For this technique to work, we need to know the number of leaf nodes in the left subtree and right subtree upfront? $\endgroup$
    – Ganesh
    Jun 17 '20 at 18:18
  • 1
    $\begingroup$ Yes, because that's the primary thing determining the order in which we're listing the subtrees - at least if use the enumeration method in the answer you cited. All the trees with one leaf in $L$ go before all the trees with two leaves in $L$, which go before all the trees with three leaves in $L$, and so on. $\endgroup$ Jun 17 '20 at 18:52
  • $\begingroup$ Thanks a lot! I implemented it in a Python program and it works perfectly! :) $\endgroup$
    – Ganesh
    Jul 2 '20 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.