A tree is a connected acyclic graph. Graphs that contain many trees are termed a forest.

A tree with \(n\) vertices has \(n - 1\) edges.
Between any two nodes, there is exactly one path.

## Node depth vs height

The depth of the node is the number of edges from the root.
The height of a node is the number of edges to it’s lowest leaf.

## Types

### Rooted trees

A rooted tree is when one vertex has been designated as the root and every edge is directed away from this root.

### Spanning trees

A spanning tree of a graph \(G\) is a connected subgraph of \(G\) which contains all vertices, but no cycles.

### Minimum spanning tree

The spanning tree that can be formed using the minimum sum of edge weights. See Kruskal’s Algorithm and Prim’s Algorithm.

### M-ary tree

\(m\)-ary trees (binary, ternary, et al) are rooted trees where every vertex has \(m\) or fewer children. An m-ary tree is *regular* if all internal nodes have exactly \(m\) children.

At level \(h\) there are a maximum \(m^h\) vertices.

## Isomorphism

General isomorphic trees are as the same as graph isomorphism.

Isomorphic rooted trees must have a mapping form the root of one tree to a root of the other. A isomorphic tree may or may not be isomorphic as a rooted tree.

## Applications