2️⃣

# 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
(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

1️⃣
2.1 Nodes

## Next Section

3️⃣
2.3 Linked Lists

⚖️
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.