A Tree Is Recursive

In a linked list, each node is followed by exactly one smaller list. If a node can refer to more than one smaller structure, we get a tree.

Here is a tree of six values:

                   ╭───╮
                   │ 3 │
                   ╰─┬─╯
           ┌─────────┴─────────┐
         ╭─▼─╮               ╭─▼─╮
         │ 5 │               │ 8 │
         ╰─┬─╯               ╰───╯
  ┌────────┼────────┐
╭─▼─╮    ╭─▼─╮    ╭─▼─╮
│ 1 │    │ 4 │    │ 9 │
╰───╯    ╰───╯    ╰───╯

A node holds a value and sits above zero or more other nodes. The arrowheads show each reference running from a node down to the node below it.

Alternative diagram

The diagrams in this coursebook draw each edge as vertical and horizontal line segments joined at the corners, so the connection from 3 down to 5 goes down, across, and down again. The same tree is often drawn with each edge as a single slanted line instead, like this:

        (3)
       /   \
     (5)   (8)
    / | \
  (1)(4)(9)

You will see this style in most textbooks and online.

Take 5 together with everything below it. It is a smaller tree on its own:

         ╭───╮
         │ 5 │
         ╰─┬─╯
  ┌────────┼────────┐
╭─┴─╮    ╭─┴─╮    ╭─┴─╮
│ 1 │    │ 4 │    │ 9 │
╰───╯    ╰───╯    ╰───╯

I did not draw the arrowheads this time. By convention the references in a tree run from top to bottom, so we can leave them off.

The same is true of 8, a tree of a single node, and of 1, 4, and 9. Every node, with everything below it, is a smaller tree. The whole tree is the value 3 sitting above two of these smaller trees.

This gives a recursive definition, in the same two-part form we used for the linked list. A tree is one of two things:

  • the empty tree, or
  • a node holding a value, above zero or more smaller trees, separate from one another.