Trees at a first look

A tree is a set of nodes (items) where each node has children and exactly one parent. The only exception is the root, the node at the top. Folders on your disk, the HTML of a web page and an organisation chart are all trees.

A binary tree gives each node at most two children. A binary search tree also keeps smaller values on the left and larger ones on the right. So finding a value takes O(log n) steps when the tree is balanced (evenly filled), and O(n) when it degrades into a long chain.

Most tree code uses recursion: handle the node, then call the same function on each child. At this stage, aim to build a small binary search tree and walk it, not to master balancing.