Unique binary search trees

Question

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)

Answer 1

Some suggestions:

• 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.

• MrJoe: 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)