- 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.

- It has one distinguished vertex called the
- 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.

- if there is an edge from A to B, then
A is the

Copyright © 1996 by David Matuszek

Last modified Feb 2, 1996