1
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ I think this tree is similar to something sometimes known as a caterpillar. $\endgroup$ – Discrete lizard Mar 21 '18 at 22:02
1
$\begingroup$

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

In Haskell this could be implemented as:

seqsTo n = concatMap (seqsToOfLength n) [1..n]
seqsToOfLength n 1 = [[n]]
seqsToOfLength n l = concatMap (\a -> map (a:) (seqsToOfLength (n-a) (l-1))) [1..n-l+1]
$\endgroup$
  • $\begingroup$ Thanks a lot! I just tested this out and it looks like it works as expected. Here's a live JS version for anyone else who needs to try it out: stackblitz.com/edit/angular-zkvfaa $\endgroup$ – Ryan Lester Mar 30 '18 at 4:15
1
$\begingroup$

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

$\endgroup$

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.