How many possible combinations of numbers make the same binary tree

Question

Setup:

I have a list of numbers that represent a Binary tree. The first number is treated differently than some of the rest, it is the root. Out of "the rest" of the numbers, some will be higher than the root, some will be lower. Higher numbers are ordered to go to the left, while younger numbers are ordered to go to the right. Example:

list = [5,7,6,8,9,2,1,3,4]
root = 5
higher = [7,6,8,9] #in order of appearance
    root = 7
    higher = [8,9]
    lower  = [6]
lower  = [2,1,3,4] #in order of appearance
    root = 2
    higher = [3,4]
    lower  = [1]

In this case, the tree would look something like this:

                                      5
                        -------------| |--------------
                       |                             |
                       7                             2
             8--------| |-------6             3-----| |-----1
         ---|                              ---|
        9                                 4

I am looking to find a way to model the number of possible combinations that the list [5,7,6,8,9,2,1,3,4] can be arranged in so that an identical binary tree is made. The solution will most definitely be recursive, in that out of the list of "higher" and "lower" numbers, they can be broken down even more.

Figuring out how many ways all the numbers can be arranged can be started by breaking down the trees as we did with the lists above.

Parents can be mixed, children can be mixed, but children and parents cannot be mixed

higher = [7,6,8,9]

But the higher list does not need to preserve its order of [7,6,8,9]. Only the items higher the root that are not parents to another tree need to be kept in order of appearance. Since 6, and 8 are both children of 7, they are interchangeable, but 9 must be before 8, since its a child of it. So basically the only rules in rearranging this list are:

• Must start with 7
• 8 must always come before 9

Therefore there are three combinations with this.

[7,6,8,9]
[7,8,6,9]
[7,8,9,6]

All of these can be broken down into identical sub-trees, so our condition is met, now we can look at the list of elements lower than the main root.

lower = [2,1,3,4]

Lower list does not need to preserve its order either, it follows similar rules and can be written three different ways to produce identical trees:

[2,1,3,4]
[2,3,1,4]
[2,3,4,1]

We now have this information: - The lower can be written 3 ways - The higher can be written 3 ways

How many different ways can they be combined to produce the same tree? Is this 3^3? Or more?

Looking at the numbers I know this:

list = [5,7,6,8,2,1,3,4]

If I make a list of possible numbers that can go in each spot, here is how far I end up getting:

First element of list must be 5, it is the root. After than it has to be a 2 or a 7, because anything else would break the order of the higher/lower lists. After that, it gets messy.

If second number = 2, the third number can be one of three things, 1, 3, or 7.

If second number = 7, the third number can be one of three things, 6, 8, or 2.

After this it expands much larger and the combinations go up very quick. My question is, is there a way to recursively retrieve the number of total possible combinations in an efficient manner? I will be doing this in python. Thank you.

Answer 1

Building on ideas above....Here is python generator code to produce all equivalent orderings.

import collections

Node = collections.namedtuple('Node', ('root','left', 'right'))

def tree_from_list(lst):
    if not lst:
        return None
    root = lst[0]
    left_lst = [x for x in lst if x > root]
    right_lst = [x for x in lst if x < root]
    return Node(root,tree_from_list(left_lst), tree_from_list(right_lst))

def parent(key, tree):
    if tree is None:
        return -1
    elif (tree.left != None) and (tree.left.root == key): 
        return tree.root
    elif (tree.right != None) and  (tree.right.root == key):
        return tree.root
    elif (key > tree.root):
        return parent(key, tree.left)
    else: return parent(key, tree.right)

def all_insert_after(key, target, seq):
    i = seq.index(key)
    for j in range(i,len(seq)):
            mylist =  seq[:j+1] + [target] + seq[j+1:]
            yield mylist

def all_equivalent_orderings(seq):
    if (len(seq)==1):
    yield seq
    else:
        z = seq[-1]
        p = parent(z, tree_from_list(seq))
        for a in all_equivalent_orderings(seq[:-1]):    
            for b in all_insert_after(p,z,a):
                yield b  

print "Here are all 630 equivalent orderings of [5,7,6,8,9,2,1,3,4]"         
for o in all_equivalent_orderings([5,7,6,8,9,2,1,3,4]):
    print o

Answer 2

From what I understand, you want the number of topological orders compatible with the graph where each node has an arc to its parent. I'll sketch a solution in untested Python. First we need a node data type.

import collections

Node = collections.namedtuple('Node', ('left', 'right'))

A tree is either None (the empty tree) or a Node where both fields are trees.

Now, the number of topological orders for the empty tree is 1, i.e., just the empty order. The number of topological orders for a nonempty tree is given by the following counting argument. The root always comes first. After the root, an arbitrary topological order for the left subtree is shuffled arbitrarily with an arbitrary topological order for the right subtree. Thus the formula is the product of three factors.

import math

def num_shuffles(left_size, right_size):  # binomial coefficient
    return (math.factorial(left_size + right_size) //
            (math.factorial(left_size) * math.factorial(right_size)))

def num_orders_and_size(tree):
    assert isinstance(tree, (type(None), Node))
    if tree is None:
        return (1, 0)
    else:
        left_num_orders, left_size = num_orders_and_size(tree.left)
        right_num_orders, right_size = num_orders_and_size(tree.right)
        return (num_shuffles(left_size, right_size) *
                left_num_orders * right_num_orders,
                left_size + 1 + right_size)

To build the tree from the list, we use recursion (there are faster ways, but this one is simplest).

def tree_from_list(lst):
    if not lst:
        return None
    root = lst[0]
    left_lst = [x for x in lst if x > root]
    right_lst = [x for x in lst if x < root]
    return Node(tree_from_list(left_lst), tree_from_list(right_lst))