You can use this implementaion online using repl.it here: Binary Search Tree

1. Introduction
2. List of Functions
3. Examples
4. Description of Functions
5. How to Use

This implementation of a binary search tree (BST) follows the Functional Programming Paradigm as it adheres to:

• Immutability
• Pure functions
• Avoiding side-effects

It also allows for any data which can be ordered using a total order to be stored (not only numbers). This is done using a strict total order.

The following functions are implemented:

• BST(strict_total_order)
• insert(tree, element)
• remove(tree, element)
• contains(tree, element)
• size(tree)
• is_empty(tree)
• get_min(tree)
• get_max(tree)
• dump(tree) **this is an impure function

Real Numbers Sorted on <

Create a BST with elements 1 - 10 sorted by the strict total order "<"

from random import shuffle
from functools import reduce

# create the list of elements to insert
elements_to_insert = [num for num in range(1, 11)]
shuffle(elements_to_insert) # ensures the tree is probabaly near minimal height

# create the BST
strict_total_order = lambda x, y : x < y
empty_bst = BST(strict_total_order)
my_bst = reduce(insert, elements_to_insert, empty_bst)

# print the contents of the BST
dump(my_bst)

without_2 = remove(my_bst, 2)
dump(without_2)

print(is_empty(my_bst))

print(size(my_bst))

print(get_min(my_bst))

The output is:

1 2 3 4 5 6 7 8 9 10
1 3 4 5 6 7 8 9 10
False
10
1

Objects

Using a BST to organize dogs. Dogs are sorted by their age first, and if their age is the same, they are sorted by name alphabetically.

from functools import reduce

# Dog class
class Dog:
	def __init__(self, name, age):
		self.name = name
		self.age = age

dog1 = Dog("Brownie", 1)
dog2 = Dog("Jack", 8)
dog3 = Dog("Spark", 4)
dog4 = Dog("Ruby", 4)
dogs = [dog1, dog2, dog3, dog4]

# order by "<" on age first, then alphabetically on name
def strict_total_order(dog1, dog2):
	age1 = dog1.age
	age2 = dog2.age
	name1 = dog1.name.lower()
	name2 = dog2.name.lower()
	if age1 != age2:
		return age1 < age2
	elif name1 != name2:
		return sorted([name1, name2])[0] == name1
	else: #names and age are equal
		return False

empty_bst = BST(strict_total_order)

dogs_bst = reduce(insert, dogs, empty_bst)

print(contains(dogs_bst, dog1))
print(contains(dogs_bst, Dog("Bear", 2)))
print(get_min(dogs_bst).name)
print(size(dogs_bst))

The output is:

True
False
Brownie
4

BST(strict_total_order)

• O(1) time
• takes a strict total order
• returns an empty BST with that total order
  
  

insert(tree, element)

• O(h) time where h is the height of tree
• takes a BST and an element
• returns a BST with the elements of tree and element
  
  

remove(tree, element)

• O(h) time where h is the height of tree
• takes a non-empty BST which contains element
• returns a BST with the elements of tree except for element
  
  

contains(tree, element)

• O(h) time where h is the height of tree
• takes a BST and an element
• returns true if element is in tree; false otherwise
  
  

size(tree)

• O(n) time where n = size(tree)
• takes a BST
• returns the number of elements in tree
  
  

is_empty(tree)

• O(1) time
• takes a BST
• returns true if tree is an empty BST; false otherwise
  
  

get_min(tree)

• O(h) time where h is the height of tree
• takes a non-empty BST
• returns the minimum element of tree
  
  

get_max(tree)

• O(h) time where h is the height of tree
• takes a non-empty BST
• returns the maximum element of tree
  
  

dump(tree)

• this is an impure function
• O(n) time where n = size(tree)
• takes a BST
• prints the elements of tree

1. Follow this link to the online editor: Binary Search Tree.

2. Replace the example in main.py with your program. You may need to create an account to modify the code.

3. Run the program by clicking the green Run button.