Data Structures

A binary search tree (BST) maintains the invariant that every node's left subtree contains only smaller values and its right subtree only larger values. Inserting a value walks the tree from the root, branching left or right at each node by comparison, until it reaches a missing child where the new node is attached. Average insertion is O(log n) when the tree is balanced; the worst case degrades to O(n) when input order produces a skewed tree, motivating self-balancing variants like AVL and red-black trees.

A binary min-heap is a complete binary tree where every parent is less than or equal to its children. Stored as an array, the children of index i live at 2i+1 and 2i+2, so the structure stays compact without explicit pointers. Each insertion appends the new value at the end and 'sifts up' — repeatedly swapping it with its parent while the parent is larger — restoring the heap property in O(log n). Heaps are the backbone of priority queues, heap sort, and shortest-path algorithms like Dijkstra's.