Linked Lists and Trees

The linked list and the tree are both recursive, and their definitions are nearly the same. What makes one a list and the other a tree?

The formal definition of a tree uses graphs, which come in a later chapter. For now, here is an intuitive picture of what makes something a tree.

A first guess is that a tree is a linked structure where nodes can have more than one reference, while in a linked list each node has only one reference. For example, in the following tree, the node 3 has two references, and the node 5 has three references:

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

A doubly linked list gives every node two references, next and prev, and it is still a linked list. So counting references does not tell a list from a tree.

A better intuition is that a tree can branch, in a way that a linked list does not. Start with a simple singly linked list:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ──▶  │ 5 │ ──▶  │ 7 │ ──▶  │ 8 │ ──▶ null
          └───┘      └───┘      └───┘      └───┘

This is like driving on a one-way street. If you are dropped at the head, or any node, you can only go one way, and you end up at the end of the list. Now make it a doubly linked list:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ 8 │ ◀─── tail
          └───┘      └───┘      └───┘      └───┘

This is now a two-way street, but you are still traveling along a single lane. A tree is a structure where you can branch off onto different lanes, and those lanes never rejoin. In the tree above, you can branch off at 3 onto two lanes, and at 5 onto three.

The key property is not branching, it is that branches remain separate. Suppose we add extra references to a linked list that skip over some nodes:

                     ┌───────────────────┐
                     │                   ▼
         ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ │ 8 │ ──▶ null
         └───┘     └───┘     └───┘     └───┘
           │                   ▲
           └───────────────────┘

This list branches, but I would still call it a linked list, not a tree, because the branches rejoin at later nodes.

A tree does not have to branch. If every node sits above at most one smaller tree, the structure still fits the recursive definition of a tree, and it looks exactly like a linked list. So a linked list is a special kind of tree: one that never branches.