Day 15

A Python Binary Search Tree

Try it!

Type commands into the terminal below to interact with a live Binary Search Tree. Supported commands: insert <n>, search <n>, delete <n>, show (prints in-order), quit.



Description


A Python implementation of a Binary Search Tree (BST) — a node-based data structure where each node holds a value and two children, with the left child always smaller and the right child always larger. The tree supports four core operations: insert (add a new value while maintaining BST ordering), search (locate a value in O(log n) average time), delete (remove a node while preserving the BST property using in-order successor replacement), and in-order traversal (return all values in sorted order). A solid exercise in recursive thinking and pointer manipulation.

View the source code


class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

class BinarySearchTree:
def __init__(self):
self.root = None

def _insert(self, node, value):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self._insert(node.left, value)
else:
if node.right is None:
node.right = Node(value)
else:
self._insert(node.right, value)

def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self._insert(self.root, value)

def search(self, node, value):
if node is None:
return False
if value == node.value:
return True
if value < node.value:
return self.search(node.left, value)
else:
return self.search(node.right, value)

def _min_value(self, node):
current = node
while current.left is not None:
current = current.left
return current

def delete(self, node, value):
if node is None:
return node
if value < node.value:
node.left = self.delete(node.left, value)
elif value > node.value:
node.right = self.delete(node.right, value)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
temp = self._min_value(node.right)
node.value = temp.value
node.right = self.delete(node.right, temp.value)
return node

def in_order(self, node, result=None):
if result is None: result = []
if node:
self.in_order(node.left, result)
result.append(node.value)
self.in_order(node.right, result)
return result

Previous Day
Next Day