Binary tree
Insert, delete, and search nodes in a binary search tree with animated transitions. Toggle AVL balancing to watch rotations keep the tree height-optimal. Run in-order, pre-order, and post-order traversals step by step. Switch to heap mode to see how a binary heap differs in structure and invariant.
BST: left < parent < right AVL: |height(L) − height(R)| ≤ 1 Heap: parent ≤ children
Binary search trees
A binary search tree (BST) stores values such that every node’s left subtree contains only smaller values and the right subtree only larger values. This invariant makes search, insert, and delete O(h) where h is the tree height. In the best case h = log n; in the worst case (sorted input) h = n, degrading to a linked list.
AVL trees
An AVL tree (Adelson-Velsky and Landis, 1962) is a self-balancing BST that maintains the invariant |height(left) − height(right)| ≤ 1 at every node. When an insertion or deletion violates this, rotations — single or double — restore balance. This guarantees O(log n) for all operations.
Rotations
A right rotation lifts the left child to become the new root of a subtree. A left rotation lifts the right child. Double rotations (left-right or right-left) handle the zig-zag cases. Watch them animate when you insert into an AVL tree.
Binary heaps
A min-heap is a complete binary tree where every parent is smaller than its children. Unlike a BST, there is no left-right ordering — only the parent-child relationship matters. Heaps support O(log n) insert and extract-min, making them ideal for priority queues.
Traversals
In-order (left, root, right) visits BST nodes in sorted order. Pre-order (root, left, right) serializes the tree structure. Post-order (left, right, root) evaluates expressions bottom-up. Level-order (breadth-first) visits by depth.