Definition of Trees

A List is a collection of elements where:

  1. Each element (except the first) has exactly 1 predecessor.

  2. Each element (except the last) has exactly 1 successor.

A Tree has property (1), but (2) is relaxed:

(2') each element has some number of successors

N-ary Tree: each element has at most N successors.

Binary Tree: N = 2. General trees can be represented using binary trees.

Root of a tree: the unique node with no predecessor.

Leaf of a tree: any node with no successor.

Children of a node: its successors.

Parent of a node: its unique predecessor.

Siblings: children of the same parent.