A simple naive implementation of a binary search tree in Python.

The purpose of this repo is to serve as an example of how to set up a GitHub Actions workflow.

A binary tree where each internal node x stores a key such that the key stored in any node in the left subtree of x is less than the key stored in x, and the key stored in any node in the right subtree of x is greater than the key stored in x.

— Paul E. Black, binary search tree, Dictionary of Algorithms and Data Structures [online], NIST.

A binary search tree is the right structure when you need ordered data with efficient search, insert, and delete operations (O(log n) on average):

• Symbol tables — compilers store variable and function names in a BST for fast lookup during parsing and code generation.
• Database indexing — BSTs underpin many index structures, enabling range queries and sorted iteration over records.
• Autocomplete — prefix-based search and suggestion engines traverse a BST to find all keys in a given range efficiently.
• Priority queues — a BST can serve as an ordered set where the minimum or maximum is always accessible at the root's leftmost or rightmost node.
• Sorting — inserting n elements and reading back with an inorder traversal produces a sorted list in O(n log n) time.

Note: An unbalanced BST degrades to O(n) in the worst case. For guaranteed performance, prefer a self-balancing variant such as a red-black tree.

from BST import BST

tree = BST()
tree.random(10)
tree.tofigure().render('./images/bst', format='png')

• Python 3.6+
• graphviz (system package) for tofigure()

Clone the repository and install dependencies:

git clone https://github.com/icaoberg/python-bst.git
cd python-bst
pip install -r requirements.txt

from BST import BST

tree = BST()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

print(tree.size())     # 5
print(tree.min())      # 1
print(tree.max())      # 7
print(tree.inorder())  # [1, 3, 4, 5, 7]
print(tree.is_empty()) # False
print(len(tree))       # 5

pytest tests.py

If you found this project helpful, consider buying me a coffee!

Copyright © icaoberg at Carnegie Mellon University. All rights reserved.