Trees
Pick an operation to watch a binary search tree grow, shrink, traverse, or rebalance — with pseudocode highlighting the line that's executing right now.
BST Insert
Inserting into a binary search tree walks down from the root, going left whenever the new value is smaller and right whenever it's larger, until it falls off the tree — that empty spot is exactly where the new node belongs. Because each comparison eliminates one whole subtree, the walk is only as long as the tree is tall (h), not as long as it has nodes.
Open visualizer
O(h) · O(h) spaceBST Delete
Deleting from a binary search tree has three cases. A leaf is simply removed. A node with one child is spliced out and replaced by that child. A node with two children can't just disappear without breaking the ordering, so it borrows its in-order successor — the smallest value in its right subtree — copies that value into place, then deletes the (now duplicate, easier) successor instead.
Open visualizer
O(n) · O(h) spaceInorder Traversal
Visits the left subtree, then the node itself, then the right subtree. On a binary search tree this always produces every value in sorted order — a free side effect of the BST ordering property, and the reason inorder is the traversal you reach for whenever you need sorted output.
Open visualizer
O(n) · O(h) spacePreorder Traversal
Visits the node itself first, then its left subtree, then its right subtree. Because a node is always recorded before its children, preorder is the traversal used to serialize a tree for later reconstruction, or to copy a tree structure top-down.
Open visualizer
O(n) · O(h) spacePostorder Traversal
Visits both subtrees before the node itself, so every node is recorded only after everything beneath it. That makes postorder the natural traversal for anything that must finish with the children before touching the parent — freeing memory bottom-up, or evaluating an expression tree.
Open visualizer
O(1) per rotation · O(1) spaceAVL Rotation
A plain BST can degrade into a straight chain if values arrive in sorted order, turning every operation into O(n). An AVL tree prevents that by tracking each node's balance factor (right subtree height minus left) and, the moment it drifts past 1 or -1, restoring balance with a rotation — a constant-time pointer rearrangement that shortens the tall side without breaking the BST ordering.
Open visualizer