2.2 Binary Trees

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
notion image
(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.


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

Previous Section

2.1 Nodes
Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.