Binary search tree
Binary search tree is an interactive experiment in Data Structures, a free simulation from StudyFi Lab that runs right in your browser.
At every node, smaller values go left and larger ones go right. Searching and inserting therefore follow a single path from the root and take O(h), where h is the tree height — for a balanced tree h ≈ log₂ n. Deleting has three cases: a leaf just disappears, a node with one child is replaced by that child, and a node with two children takes the value of its in-order successor. An in-order traversal lists the values sorted; similar trees power database indexes.
Try this: Delete the root — it has two children, so you will see the successor search. Then try “Insert sorted values”: the tree degenerates into a list and the height grows to n.
Frequently asked questions
What does the “Binary search tree” experiment show?
At every node, smaller values go left and larger ones go right. Searching and inserting therefore follow a single path from the root and take O(h), where h is the tree height — for a balanced tree h ≈ log₂ n. Deleting has three cases: a leaf just disappears, a node with one child is replaced by that child, and a node with two children takes the value of its in-order successor. An in-order traversal lists the values sorted; similar trees power database indexes.
How do I try “Binary search tree”?
Delete the root — it has two children, so you will see the successor search. Then try “Insert sorted values”: the tree degenerates into a list and the height grows to n.
Studying for a test?
Upload your notes and StudyFi turns them into flashcards, tests and podcasts.