Binary Search Trees

Discrete Math · Axiom Academy

A fundamental data structure that organizes data hierarchically for efficient searching, insertion, and deletion operations. 1. What is a Binary Search Tree? All keys in the left subtree are less than the node's key All keys in the right subtree are greater than the node's key Both left and right subtrees are also BSTs (recursive property) This ordering property makes BSTs incredibly efficient. To find any value, we only need to look at one path from root to leaf, never the entire tree. The search operation leverages the BST property to efficiently locate a value. Starting at the root, we compare the target with the current node: In a balanced BST with n nodes, search takes O(log n ) time on average. In the worst case (completely unbalanced), it degrades to O( n ). Insertion follows the same path as search. We traverse the tree comparing values until we find an empty spot (null child) where the new node belongs: The insertion algorithm is simple and elegant. Like search, it takes O(log n ) time on average in a balanced tree. Deletion is the most complex operation, with three cases to handle: Binary Search Trees are fundamental to many systems you use every day: Efficiency: O(log n ) operations beat linear search's O( n ) Dynamic: Unlike sorted arrays, BSTs handle insertions/deletions efficiently Ordered: Maintain sorted order without expensive sorting operations

This is the written version of the interactive lesson above. See the full Discrete Math course.