Find How Many Leaves a Ternary Tree Graph Has

Question

I stumbled across a problem while programming and was wondering if it had a nice mathematical solution. This is my first post, hopefully I follow your rules well and my terminology is understandable. The problem is as follows:

Setup:

• Given a list of numbers like {1,2,3,5,8,9,10}
• You can move at most +3 from the number you are on to the next number
• You must start on the lowest number and end on the highest number
• Assume that the numbers allow for a solution

For the numbers {1,2,3,5,8,9,10} the tree would look like:

                     1
                  ┌──┴──┐
                  3     2     
           ┌──────┘  ┌──┴──┐
           5         5     3
           │         │     └─────┐
           8         8           5
        ┌──┴──┐   ┌──┴──┐        │ 
        9     10  9     10       8
        │         │           ┌──┴──┐ 
        10        10          9     10  
                              │
                              10

It has 6 total leaves. The problem could be solved by programmatically creating all possible paths then counting them, but that's boring and slow. Is there some way to count the leaves without having to do that?

Answer 1

I believe the problem is to count the number of such paths. This problem can be solved for general graphs, and in this case using a recurrence.

Let the numbers be $a_1<a_2<\ldots<a_n$. Let $f(k)$ denote the number of paths from $a_1$ to $k$.

The recurrence is: $f(k)=f(k-1)g(k-1)+f(k-2)g(k-2)+f(k-3)g(k-3)$, where $g(i)=1$ if $i$ is present in the sequence and $g(i)=0$ otherwise. The last step to $k$ could have been from one of $k-1,k-2,k-3$ which explains the recurrence.

The values $f(k)$ can then be computed in order for $k=a_1,a_2,\ldots,a_n$.