Skip to content

Instantly share code, notes, and snippets.

@simsicon simsicon/bst.py
Created Aug 30, 2016

Embed
What would you like to do?
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.