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.
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.
A rooted tree is when one vertex has been designated as the root and every edge is directed away from this root.
A spanning tree of a graph \(G\) is a connected subgraph of \(G\) which contains all vertices, but no cycles.
The spanning tree that can be formed using the minimum sum of edge weights. See Kruskal’s Algorithm and Prim’s Algorithm.
\(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.
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.