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