# Calculating unbalanced binary trees

Two-part question:

1. Is there any more specific name than "unbalanced binary tree" to describe the tree below? The distinguishing characteristics are:

i. The root node and left children must have either 0 or 2 children.

ii. Right children must have 0 children.

iii. All nodes must be positive non-zero integers.

iv. Any node with children must equal the sum of its children.

2. Given the value of the root node (in this case, 77), is there a standard algorithm to efficiently calculate all possible trees of this type?

• i.e. (77, 76, 1), ..., (77, 1, 76), (77, (76, 75, 1), 1), etc.

         77
/  \
68   9
/  \
48   20
/   \
47    1
/  \
42   5

• I think this tree is similar to something sometimes known as a caterpillar. – Discrete lizard Mar 21 '18 at 22:02

Here is an algorithm to enumerate all possible trees meeting your conditions. These trees are in bijection with their sequence of leaves. Given a root value $n$, iterate sequence lengths from 1 to $n$. For a length $l$ you wish to enumerate all sequences of positive numbers of length $l$ adding to $n$. If $l=1$ choose the sequence consisting of $n$. If $l>1$ enumerate possibilities 1 to $n-l+1$ for the first number $a$ and generate remaining numbers as a sequence of length $l-1$ adding to $n-a$.
seqsTo n = concatMap (seqsToOfLength n) [1..n]

It is a special caterpillar. Let $d(i)$ be the number of such trees with root $i$. We have $d(1)=1$; and $d(n)=\sum_{i=1}^{n-1}d(i)+1$, where "plus 1" is for the case of no children and $d(i)$ in sigma for the case that the left child is $i$. One can easily compute $d(n)$ in $O(n)$ time using a simple loop. Or it is not hard to solve the recurrence relation and get $d(i)=2^{i-1}$ for $i\geq 1$.