I have written some code that prints out all unique pre-ordered binary search trees containing numbers 1 to n.
It is not an especially efficient solution and has a time complexity (I believe) of O(n!) but hopefully it is fairly easy to understand.
As I am using sets the output is not sorted.
"""Module constructs and prints unique BST."""
import itertools
class Node():
"""Builds a BST"""
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def add_node(self, value):
"""Adds new elemenet to binary search tree."""
if self.value:
if value > self.value:
if not self.right:
self.right = Node(value)
else:
self.right.add_node(value)
else:
if not self.left:
self.left = Node(value)
else:
self.left.add_node(value)
def print_tree(self):
"""Return the BST as a string"""
string_tree = ""
if self.value:
string_tree += (str(self.value) + " ")
if self.left:
string_tree += self.left.print_tree()
if self.right:
string_tree += self.right.print_tree()
return string_tree
def build_BST(permutation):
"""Builds a BST from a list of numbers"""
if permutation:
tree = Node(permutation[0])
for i in range(1, len(permutation)):
tree.add_node(permutation[i])
string_tree = tree.print_tree()
return string_tree
return False
def build_trees(size_tree):
"""Build BST containing numbers in range 1 to n"""
if not isinstance(size_tree, int):
print("Please enter an integer")
return
if size_tree <= 0:
print("Function only prints trees with numbers >= 1")
return
permutations = list(itertools.permutations([i for i in range(1, size_tree + 1)],
size_tree))
set_solutions = set()
for permutation in permutations:
string_tree = build_BST(permutation)
set_solutions.add(string_tree)
for solution in set_solutions:
print(solution)
print(f"==========\n{len(set_solutions)} solutions.")
if __name__ == "__main__":
build_trees(4)
