Binary search trees – insert, search, delete and tree traversals
Computer ScienceAlgorithms & Problem SolvingAges 17–18
Loading…
Sign in to playInsert, search for and delete keys in a binary search tree and watch the comparison path through each node, the tree height and the number of comparisons; deleting a node with 0, 1 or 2 children uses the in-order successor. Inserting sorted keys makes the tree degenerate into a list, which a results table compares with random and balanced insertion orders. A Traversal mode steps through pre-order, in-order, post-order and level-order traversal, and an Expression tree mode gives prefix, infix and postfix notation.
Lesson: Binary trees and binary search trees; pre-order, in-order, post-order and breadth-first traversal; expression trees and Polish notation
What it shows
A binary search tree keeps every key in the left subtree smaller and every key in the right subtree larger than the key of the node, so searching, inserting and deleting follow a single path from the root and need at most h + 1 comparisons, where h is the height. Random insertion orders give fairly short trees, but sorted input produces a chain as slow as linear search. Traversals visit every node once: depth-first orders use the call stack of a recursive function, level order uses a queue, and on expression trees they produce prefix, infix and postfix notation.
How to use
In Binary search tree mode, type a Key and click Insert, Search or Delete; the comparisons are shown step by step. Choose an Insertion order and a Number of keys, then click Build new tree to add a row to the comparison table. In Tree traversal mode, pick a Traversal and click Play or Step. In Expression tree mode, choose an expression or type your own.
Parameters you can change
- Mode Binary search tree, Tree traversal, Expression tree
- Initial insertion order Random, Ascending (sorted), Middle key first (balanced)
- Initial number of keys 3–15 keys
- Initial keys to insert (numbers 1–99, e.g. 50 30 70; empty = generated)
- Traversal Pre-order (NLR), In-order (LNR), Post-order (LRN), Level-order (BFS)
- Sample expression (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, Custom
- Custom expression (empty = use the sample expression)
- Run speed 0.5–4 steps/s
Questions to explore
- How tall is the tree when seven keys are inserted in ascending order, and how many comparisons find the largest key?
- Why does an in-order traversal of a binary search tree always list the keys in ascending order?
- How is (3 + 4) * 5 written in postfix notation, and why are no brackets needed?
