Trees and Binary Search Trees
A structure of nodes with one root and no cycles, and the binary search tree rule that keeps smaller values left and larger values right. Walking the tree left, node, right returns the values in sorted order.
What a learner can do afterwards
- Insert a run of values into an empty binary search tree and draw the result
- Search for a value and count the comparisons against the tree's height
- Walk a tree in order and show that the output comes out sorted
1 · Read
A tree is nodes with one root and no cycles, where each node holds a value and links to children. In a binary search tree every node has at most two children, with smaller values left and larger values right. The first value you insert into an empty tree becomes the root.
Insert 5, 2, 8, 1, 3 in that order and watch the rule work. 5 becomes the root, 2 goes left, 8 goes right, 1 goes left of 2, and 3 goes left of 5 then right of 2. So 3 lands as the right child of 2.
You search by comparing at each node and counting one comparison per visit. Finding 3 visits 5, then 2, then 3, which is 3 comparisons. Sorted arrivals are the trap: inserting 1 through 7 in order chains every node right, and searching that chain costs like a linked list instead of a short bushy tree.
You check any tree with an in order walk: left subtree, then the node, then the right subtree. For the example tree that prints 1, 2, 3, 5, 8, sorted smallest to largest. If your walk is unsorted, one value sits on the wrong side.
Smaller left and larger right keeps order, and an in order walk prints values sorted.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.