bst.py

import math

class Tree:
    def __init__(self, seq):
        self.root = seq[0]
        self.left_seq, self.right_seq = [], []

        if len(seq) == 1:
            self.leaf = True
            self.left = None
            self.right = None
        else:
            self.leaf = False
            for i in range(1, len(seq)):
                entry = seq[i]
                if entry < self.root:
                    self.right_seq.append(entry)
                else:
                    self.left_seq.append(entry)

            if len(self.left_seq) == 0:
                self.left = None
            else:
                self.left = Tree(self.left_seq)

            if len(self.right_seq) == 0:
                self.right = None
            else:
                self.right = Tree(self.right_seq)

    def possible_seqs_num(self):
        left_len = len(self.left_seq)
        right_len = len(self.right_seq)
        upper = math.factorial(left_len + right_len)
        lower = (math.factorial(left_len) * math.factorial(right_len))
        combinations = upper / lower

        left_possible_seqs_num = 1 if self.left is None else self.left.possible_seqs_num()
        right_possible_seqs_num = 1 if self.right is None else self.right.possible_seqs_num()

        return combinations * left_possible_seqs_num * right_possible_seqs_num
        

import random

seq = range(1, 50)
random.shuffle(seq)
t = Tree(seq)
print t.possible_seqs_num()