# Unique binary search trees

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
"""Adds new elemenet to binary search tree."""
if self.value:
if value > self.value:
if not self.right:
self.right = Node(value)
else:
else:
if not self.left:
self.left = Node(value)
else:
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)):
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):
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)
for solution in set_solutions:
print(solution)
print(f"==========\n{len(set_solutions)} solutions.")

if __name__ == "__main__":
build_trees(4)



• You can use sys.argv or argparse to pass the size on the command line. The latter can check the type and range for you, and print an appropriate error message and usage string. You can specify a validator function in the type argument to check for non-trivial values.
• print_tree does not print the tree, it returns a string representation of it. That is the job of __str__, a special internal method you can override to define the string representation of a class.
• "node" in add_node is redundant.
• Running this code through black will improve the formatting slightly. flake8 and mypy (with a strict configuration) can help make the code more idiomatic.
• I can see how argparse can throw a non int error. But I can't work out how to throw a neat out of range error (the choices argument is very ugly) – EML Jun 10 at 17:29