BitWithBite
Discrete Mathematics · Quick Reference
Trees Cheat Sheet
In one line: a tree is a special type of graph with no cycles — a natural way to represent hierarchies, from family trees to file systems to decision-making processes.
Key Ideas
1Definition. A tree is a connected graph with no cycles. A tree with n vertices always has exactly n-1 edges.
2Root, Parent, Child. In a rooted tree, one vertex is designated the root; every other vertex has exactly one parent and can have multiple children.
3Leaf Node. A vertex with no children (degree 1 in an undirected sense, aside from the root).
4Height and Depth. The depth of a node is its distance from the root; the height of the tree is the maximum depth of any node.
5Binary Tree. A tree where every node has at most 2 children, commonly used in computer science for efficient searching and sorting.
Worked Examples
A tree has 8 vertices. How many edges does it have?
7 edges
A tree has 12 edges. How many vertices does it have?
13 vertices
In a rooted tree, node X has children Y and Z, and Y has child W. Find the depth of W (root has depth 0).
Depth of W = 2
Formulas
A tree with n vertices has exactly n-1 edges
Practice Yourself
A tree has 6 vertices. Find the number of edges.
5
A tree has 20 edges. Find the number of vertices.
21
What is a 'leaf node'?
A node with no children