Electrical & Computer
Binary Search Tree Lab
A binary search tree keeps one simple promise: every value to the left of a node is smaller, every value to the right is larger. This lab lets you build one by inserting values and then SEARCH for a target — the path from the root lights up so you can see search skip half the remaining tree at every step, which is what makes lookups O(log n) in a balanced tree. Delete a node and watch all three classic cases handled (a leaf vanishes, a one-child node is bypassed, a two-child node is replaced by its in-order successor), with the tree staying sorted throughout. The catch is built in too: insert values in already-sorted order and the tree collapses into a lopsided chain of height n−1, where search degrades all the way back to O(n) — the very reason self-balancing trees exist. An in-order traversal of any BST always comes out sorted, and the height readout shows you exactly how good (or bad) your tree's shape is.
3
Height (edges)
12
Nodes
O(4)
Search ≈
Every left child is smaller, every right child larger. That ordering lets search skip half the tree at each step — O(log n) when balanced. Insert values in sorted order, though, and the tree degrades into a chain (height = n−1) where search is back to O(n).
How to use this simulation
A binary search tree keeps one simple promise: every value to the left of a node is smaller, every value to the right is larger. This lab lets you build one by inserting values and then SEARCH for a target — the path from the root lights up so you can see search skip half the remaining tree at every step, which is what makes lookups O(log n) in a balanced tree. Delete a node and watch all three classic cases handled (a leaf vanishes, a one-child node is bypassed, a two-child node is replaced by its in-order successor), with the tree staying sorted throughout. The catch is built in too: insert values in already-sorted order and the tree collapses into a lopsided chain of height n−1, where search degrades all the way back to O(n) — the very reason self-balancing trees exist. An in-order traversal of any BST always comes out sorted, and the height readout shows you exactly how good (or bad) your tree's shape is.
Everything runs in your browser — no sign-up, no download. Change a value and the result updates instantly, so you can build a feel for how each input shapes the outcome. It pairs with Crameleon's practice exams and step sheets when you want to go from intuition to working the problems.