Narrowing to Binary Trees

A general tree lets a node have any number of children. The most common kind of tree is the binary tree. It limits that number to two and gives the two children fixed positions.

In a binary tree, each node has at most a left child and a right child, and either one may be missing. In a general tree, a node’s children have no order among them. In a binary tree, “left” and “right” are different positions. In the tree below, 5 has a left child and no right child. If 1 were the right child of 5 instead, that would be a different binary tree.

       ╭───╮
       │ 3 │
       ╰─┬─╯
    ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮
  │ 5 │     │ 8 │
  ╰─┬─╯     ╰───╯
  ┌─┘
╭─┴─╮
│ 1 │
╰───╯

A binary tree has the same kind of recursive definition as a general tree. It is one of two things:

• the empty tree, or
• a node holding a value, with a left binary tree and a right binary tree.

A missing child is represented by the empty tree.

We have already met binary trees in this chapter. Merge sort’s call tree is one: each call on more than one element makes two recursive calls.

                    mergeSort([3, 8, 5, 2])
              ┌───────────────┴─────────────────┐
      mergeSort([3, 8])                mergeSort([5, 2])
      ┌───────┴───────┐                 ┌───────┴───────┐
mergeSort([3])   mergeSort([8])   mergeSort([5])   mergeSort([2])

Binary search compares the target to the middle element, then looks in the left half or the right half. If we draw every choice it could make on the sorted array [10, 20, 30, 40, 50, 60, 70], we get a binary tree:

         40
    ┌─────┴─────┐
   20           60
 ┌──┴──┐     ┌──┴──┐
10     30   50     70

The root, 40, is the element binary search checks first. Its left child is the element it checks next if the target is smaller, its right child if the target is larger, and so on down. This tree is called binary search’s decision tree. We will come back to this tree in a later chapter, where we build a binary search tree that holds values in this shape.