"""Binary Search Tree
Included:
- Insert
- Find data/ minimum/ maximum
- Size
- Height
- Traversals (Inorder, preorder, postorder)
- Test Code for it
Not included:
- Delete
- Display (as 2D BST)
and others...
"""
class Node: # Node
def __init__(self, data, start=None):
self.data = data
self.left = self.right = start
class BinarySearchTree:
def __init__(self):
self.root = None
# Insert a node
def put(self, data):
if self.root is None: # BST empty
self.root = Node(data)
else:
curr = self.root # initialise curr pointer
while curr:
if data < curr.data: # data put at left
if curr.left:
curr = curr.left
else: # no left child
curr.left = Node(data)
break
else: # data put at right
if curr.right:
curr = curr.right
else: # no right child
curr.right = Node(data)
break
def find(self, data):
curr = self.root # start from root
while curr:
if data < curr.data: # data at left
curr = curr.left
elif data > curr.data: # data at right
curr = curr.right
else:
return True # found
return False
def min_of(self):
curr = self.root # start from root
while curr.left:
curr = curr.left # keep going left
return curr.data
def max_of(self):
curr = self.root # start from root
while curr.right:
curr = curr.right # keep going right
return curr.data
def size(self):
def go(node): # helper
if node:
return 1 + go(node.left) + go(node.right)
return 0
return go(self.root)
def height(self):
def go(node): # helper
if node:
return 1 + max(go(node.left), go(node.right))
return -1 # it has -1 if empty
return go(self.root)
# In_order
def in_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
go(node.left) # left
lst.append(node.data) # Node
go(node.right) # Right
go(self.root)
return lst
# Pre_order
def pre_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
lst.append(node.data) # Node
go(node.left) # left
go(node.right) # Right
go(self.root)
return lst
# Post_order
def post_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
go(node.left) # left
go(node.right) # Right
lst.append(node.data) # Node
go(self.root)
return lst
# Test
from random import randint, sample
def BST_tester(BST):
r = randint(5, 10)
lst = [randint(10, 100) for _ in range(r)]
print(f"List: {lst}",
f"Sorted: {sorted(lst)}",
sep = "\n", end = "\n\n")
B = BST()
for item in lst:
B.put(item)
lst.sort()
print("AFTER INSERTION:",
f"Size: {B.size()} | {B.size() == len(lst)}",
f"Height: {B.height()} | I can't code the display for this",
f"Min: {B.min_()} | {B.min_() == min(lst)}",
f"Max: {B.max_()} | {B.max_() == max(lst)}",
sep = "\n", end = "\n\n")
items = sample(lst, 5) + [randint(10, 100) for _ in range(5)] # 5 confirm in list, 5 might be in list
found = [B.find(_) for _ in items]
zipped = list(zip(items, found))
inlst, notinlst = zipped[:5], zipped[5:]
print(f"Sampled from lst: {inlst} | All True: {all(found[:5])}",
f"Random: {notinlst}",
sep = "\n", end = "\n\n")
print(f"Inord: {B.in_ord()} | Correct Insertion: {lst == B.in_ord()}",
f"Preord: {B.pre_ord()}",
f"Postord: {B.post_ord()}",
sep = "\n")
BST_tester(BST)