Anatomy of a Tree

A tree has standard names for its parts. Consider this tree:

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

A node is one piece of the tree: a value together with the references to the nodes directly below it. This tree has six nodes.

An edge is one of those references, drawn as a line from a node to one directly below it.

The root is the node at the top, with nothing above it. Here it is 3. Every non-empty tree has exactly one root.

When an edge runs from one node down to another, the upper node is the parent and the lower is its child. So 3 is the parent of 5 and 8, which are its children. Every node has exactly one parent, except the root, which has none. A node may have any number of children.

Two nodes with the same parent are siblings. Here 1, 4, and 9 are siblings, and so are 5 and 8.

A leaf is a node with no children. The leaves here are 1, 4, 9, and 8. A node that does have children is an internal node. The internal nodes here are 3 and 5.

A node together with everything below it is a subtree. We saw these when we defined a tree. There we called them smaller trees. The subtree rooted at 5 is 5 with its children 1, 4, and 9. Every node is the root of its own subtree, and the whole tree is the subtree rooted at the root.

The nodes in a node’s subtree, other than the node itself, are its descendants. The descendants of 5 are 1, 4, and 9. Going the other way, a node’s parent, its parent’s parent, and so on up to the root are its ancestors. The ancestors of 9 are 5 and 3.