Binary Search Trees study song
Quick answer
A binary search tree stores values so that everything in a node's left subtree is smaller and everything in the right subtree is larger. That one rule lets search, insert and delete skip half the tree at each step.
Exams test the three depth-first traversals, tracing an insertion, deleting a node with two children, and explaining why an unbalanced tree is slow. Traversal order is the part students mix up most, since the names only describe when the root is visited. A melody with a repeating left, root, right pattern gives your memory a path to walk through the tree, and a second verse can cover what changes when the tree is balanced by AVL rotations.
5 facts to know about binary search trees
- 1In a binary search tree, every left descendant is smaller than the node and every right descendant is larger.
- 2An in-order traversal (left, node, right) of a binary search tree visits keys in sorted order.
- 3Search, insert and delete take O(h) time, which is O(log n) for a balanced tree and O(n) for a degenerate one.
- 4Inserting already sorted keys into a plain binary search tree produces a linked-list shape with height n.
- 5An AVL tree keeps the height difference between any node's two subtrees to at most 1, using rotations.














