Trees

• Importance: Trees are used in some algorithms.

• A tree is a kind of digraph:
  • It has one distinguished vertex called the root;
  • There is exactly one path from the root to each vertex; and
  • The level of a vertex is the length of the path to it from the root.

• Terminology:
  • if there is an edge from A to B, then A is the parent of B, and B is the child of A.

  • A leaf is a node with no children.

  • The height of a tree is the largest level number of any vertex.