2
\$\begingroup\$

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)

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – EML Jun 10 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.