Objective
Insert keys into a binary search tree and watch the ordering rule build the shape, then verify that an inorder walk comes out sorted.
The idea
Each new key falls left or right of every node it meets. The rule is tiny, but it arranges the whole structure - and a sorted traversal falls out for free.
Try this
- 1Insert a balanced mix of keys and admire the shape.
- 2Insert keys in ascending order and see the tree degenerate.
- 3Delete a node and watch how its children are reattached.
- 4Run the inorder traversal and check it is sorted.
Watch for
- Left subtree < node < right subtree at every level.
- Inorder traversal is the data, already sorted.
- Insert order decides the shape - and the search cost.
- A degenerate tree is just a slow linked list.