Picture an ancestry chart: from each person, you can branch to two biological parents. A binary tree follows that two-way limit. Each node has at most two children, traditionally called its left child and right child. A node can also have just one child or none. section 7.5
The ancestry example makes the connections easy to picture, but a binary tree can hold arbitrary data. The nodes below a left or right child form that child’s subtree. Like other trees, a binary tree has no cycles. section 7.5 section 7.7
Finding a number
Suppose a binary search tree has 10 at its root, with 5 to the left and 20 to the right. Looking for 7? Go left from 10 because 7 is smaller, then right from 5 because 7 is larger. You can ignore the other branches. That shortcut comes from the search tree’s extra rule: values in a node’s left subtree are smaller, and values in its right subtree are greater. The two-child limit alone does not give you that rule. section 8.2
Binary trees have other jobs, too. Huffman coding uses them for text compression. A balanced binary search tree uses the same two-child shape with additional rules aimed at fast searching. The shape is a starting point; what the tree does depends on the rules and data you put in it. section 7.6 section 8.2
