Binary Trees

Now that we know about Nodes, we can begin to talk about Binary Trees. Sometimes called Binary Search Trees (BST’s), Binary Trees are an efficient way to retrieve data. They act very similarly to python dictionaries: they store values and associate them with keys. However, the main difference is in how they work.

How They Work

BST’s store keys in an ordered way. Specifically, each node in a BST has exactly two child nodes. The key in each BST node is greater than the key in the node’s left child and less than the key in its right child. This also means that, on a bigger scale, the key in each node will be greater than all the keys in the left subtree and less than all the keys in the right subtree.

Here’s an example of how a BST might look. As you can see, each node is greater than all the nodes to the left and less than all the nodes to the right

(Image courtesy of Geeks For Geeks)

BST’s vs built-in dictionaries

Pro-BST : Memory and Sorted order

• BST’s make retrieval in sorted order a lot easier than built-in dictionaries. (since they’re naturally sorted with the least key on the leftmost node and greatest key on the rightmost node)
• BST’s tend to be more memory efficient than built-in dictionaries since they only allocate nodes when needed.

Pro-dictionary : Speed

• dictionaries take on average O(1) time to retrieve or insert while BST’s take (if they’re balanced) O(log(n)) on average to retrieve or insert.

Python Implementation

class Node:
    # this class is meant to be used with BinaryTree
    def __init__(self, key, value) -> None:
        self.key = key
        self.value = value
        self.left = None
        self.right = None

    def __str__(self) -> str:
        ret = ""
        if self.left is not None:
            ret += str(self.left)
        ret += self.plain_str() + "\\n"
        if self.right is not None:
            ret += str(self.right)
        return ret

    def height(self) -> int:
        if self.left is None and self.right is None:
            return 1
        if self.left is not None and self.right is None:
            return 1 + self.left.height()
        if self.right is not None and self.left is None:
            return 1 + self.right.height()
        return 1 + max(self.left.height(), self.right.height())

    def plain_str(self) -> str:
        return str(self.key) + ": " + str(self.value)

class BinaryTree:
    def __init__(self, default_val=None) -> None:
        self.root = None
        self.default_val = default_val

    def recursive_contains_key(self, key, current) -> bool:
        if current is None:
            return False

        if current.key == key:
            return True

        if key < current.key:
            return self.recursive_contains_key(key, current.left)
        return self.recursive_contains_key(key, current.right)

    def contains_key(self, key) -> bool:
        return self.recursive_contains_key(key, self.root)

    def recursive_add(self, key, value, current):
        if current.key == key:
            current.value = value
            return True
        if key < current.key:
            if current.left is not None:
                return self.recursive_add(key, value, current.left)
            current.left = BinaryTree.Node(key, value)
            return True

        if current.right is not None:
            return self.recursive_add(key, value, current.right)
        current.right = BinaryTree.Node(key, value)
        return True

    def add(self, key, value) -> bool:
        if self.root is None:
            self.root = BinaryTree.Node(key, value)
            return True
        return self.recursive_add(key, value, self.root)

    def recursive_get(self, key, current):
        if current is None:
            raise Exception("KEY NOT FOUND")
        if current.key == key:
            return current.value
        if key < current.key:
            return self.recursive_get(key, current.left)
        return self.recursive_get(key, current.right)

    def get(self, key):
        return self.recursive_get(key, self.root)

    def __setitem__(self, key, value):
        self.add(key, value)

    def __getitem__(self, key):
        return self.get(key)

    def __str__(self) -> str:
        ret = "{\\n"
        if self.root is not None:
            ret += str(self.root)
        ret += "}"
        return ret

    def __repr__(self) -> str:
        return str(self)

    def print_structure(self) -> None:
        if self.root is None:
            print("{}")
            return

        height = self.root.height()
        spacing = 6
        total_width = spacing * (2**height)

        # print top divider
        print("-" * total_width)

        current_generation = [self.root]
        next_generation = []
        for i in range(1, height + 1):
            margin_between = int(
                (total_width - spacing * (2 ** (i - 1))) / ((2 ** (i - 1)) + 1)
            )
            for node in current_generation:
                print(" " * margin_between, end="")
                if node is None:
                    print(" " * spacing, end="")
                    next_generation.extend([None] * 2)
                else:
                    print(node.plain_str(), end="")
                    next_generation.extend([node.left, node.right])
            # print a newline
            print()

            current_generation = next_generation
            next_generation = []

        # print bottom divider
        print("-" * total_width)

myBinaryTree = BinaryTree()
myBinaryTree[33] = 22
myBinaryTree[22] = 11
myBinaryTree[44] = 33
myBinaryTree[55] = 22
print(myBinaryTree)

# to see how it internally arranges data
myBinaryTree.print_structure()

View code on GitHub.

Practice

Basic BST

Let's create a very basic version of a BST that only has insertion capabilities. Your task will be to fill in the node class and the BST class

💻 Template code

✅ Solution code