01 Key Concepts
Definition
A tree is a connected graph with no cycles. A tree with n vertices always has exactly n-1 edges.
Root, Parent, Child
In a rooted tree, one vertex is designated the root; every other vertex has exactly one parent and can have multiple children.
Leaf Node
A vertex with no children (degree 1 in an undirected sense, aside from the root).
Height 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.
Binary Tree
A tree where every node has at most 2 children, commonly used in computer science for efficient searching and sorting.
Spanning Tree
A subgraph of a connected graph that includes every vertex, is itself a tree, and uses the minimum number of edges needed to stay connected.
02 Key Formulas
- A tree with n vertices has exactly n-1 edges
03 Solved Examples
- Apply the rule: edges = n - 1 = 8 - 1.
- Rearrange the rule: n = edges + 1 = 12 + 1.
- The root is depth 0. If X is the root, X has depth 0.
- Y (child of X) has depth 1.
- W (child of Y) has depth 2.
04 Practice Questions
📄 Trees — Downloadable Worksheet
10 questions with a full answer key. Grab the PDF to print, or try the interactive version in your browser.