BST implementation for insert (put) and contain (search) in Python

Here's what I think is the main drawback of your design. You can think of a tree as being either:

1. An (empty) leaf
2. A node containing a value and having left and right branches which are themselves trees

It would be nice if these two possibilities were clearly modelled in your code. However, you've used two ways of representing a leaf, either as None (e.g., when node.right == None, that means that node has a leaf on its right branch) or as a node with value None (e.g., when you create a new, empty tree, it's just a leaf, but you represent it as a Node with value == None).

I know you thought about this issue already, since you have a #self.root = None line commented out in your source.

As a result, throughout your code, you've got a lot of mostly redundant checks like:

if node is None or node.value is None:
    ...

where the node.value is None part is really only an issue at the root (since the tree should otherwise have no nodes with value None, unless you've put a None in your tree).

It also leads to some weird behavior:

> t = BinarySearchTree()
> t.put(None)
> t.put(None)
> t.put(3)
> t.put(None)
TypeError: unorderable types: NoneType() < int()
>

You could argue that the type error makes sense, but why wasn't it thrown when we put 3 in the tree?

Anyway, a side effect of this design choice is that you've had to move all of the logic into the BinarySearchTree object, and the Node object is just a method-less data container. That's because, given a "node", you never know whether it's (1) a None; (2) a Node that contains a valid value or; (3) a Node that contains a None. You need to handle cases (1) and (3) with similar logic, so it's pointless to put the logic for case (3) in the Node (because you need to do the same thing in case (1) where you don't have a Node). Therefore, logic for cases (1) and (3) has to go in the BinarySearchTree, and when you've gotten that far, you might as well stick logic for case (2) in there, too.

Try the following exercise. Create two objects, one to represent Nodes that contain values, and one to represent Leafs that don't:

class Leaf:
    def __init__(self):
        pass

class Node:
    def __init__(self, value):
        self.value = value
        self.left = Leaf()
        self.right = Leaf()

Now, create a Tree object that dispatches to its self.root -- this root will initially be a Leaf when the tree is empty, but will change to a Node when we put something in the tree.

class Tree:
    def __init__(self):
        self.root = Leaf()

    def put(self, value):
        if value is not None:
            self.root = self.root.put(value)

    def contains(self, value):
        return self.root.contains(value)

    def in_order_traversal(self):
        return self.root.in_order_traversal()

Now, see if you can implement your tree by only adding put, contains, and in_order_traversal methods to the Leaf and Node objects, and see how that design works.

Note that you should maintain two invariants on Nodes:

1. node.value is always a valid value (never a None)
2. node.left and node.right are always either Leafs or Nodes (never a None)

SPOILERS...

Here was my solution. It passes your test, and I think it represents a cleaner design. Instead of differentiating between leafs and nodes using conditional statements in the Tree object, that decision is made by dispatching to either a Node or Leaf class. The downside is that it splits up the logic for a particular operation into two functions in different classes (so to "understand" put, you need to look at the implementations in both the Leaf and Node classes), but that's a pretty typically issue in object-oriented designs, so people are used to it.

class Leaf:
    def __init__(self):
        pass

    def put(self, value):
        return Node(value)

    def contains(self, value):
        return False

    def in_order_traversal(self):
        return []

class Node:
    def __init__(self, value):
        self.value = value
        self.left = Leaf()
        self.right = Leaf()

    def put(self, value):
        if value < self.value:
            self.left = self.left.put(value)
        else:
            self.right = self.right.put(value)
        return self

    def contains(self, value):
        if value < self.value:
            return self.left.contains(value)
        elif value > self.value:
            return self.right.contains(value)
        else:
            return True

    def in_order_traversal(self):
        return self.left.in_order_traversal() \
            + [self.value] + self.right.in_order_traversal()

class Tree:
    def __init__(self):
        self.root = Leaf()

    def put(self, value):
        if value is not None:
            self.root = self.root.put(value)

    def contains(self, value):
        return self.root.contains(value)

    def in_order_traversal(self):
        return self.root.in_order_traversal()

appending to @K. A. Buhr's answer, just for your tests, manual additions looks a bit out. try a loop

from

    self.search_tree.put(3)
    self.search_tree.put(1)
    self.search_tree.put(2)
    self.search_tree.put(5)

to

    for num in [3, 1, 2, 5]:
        self.search_tree.put(num)

which saves some lines, improving code redability !