Tree terminology
A compact glossary of words used everywhere in tree algorithms and in the rest of this tutorial. Definitions follow common textbook usage; minor variations exist across sources.
Tables on this page
- Structure — nodes, edges, relationships
- Size and levels — depth, height, degree
- Paths and subtrees — ancestors, descendants
- Binary-tree words — left/right child, full, complete
1) Structure
| Term | Meaning |
|---|---|
| Tree | A finite set of nodes with a root; connected, undirected when viewed as a graph, and acyclic (no loops). |
| Root | The unique node with no parent; the top of the hierarchy. |
| Node | An element of the tree that may store data (a key or payload). |
| Edge | A link between a parent and a child (one edge per parent–child pair). |
| Parent / child | If an edge goes from A down to B, A is the parent and B is the child. |
| Sibling | Nodes that share the same parent. |
| Leaf | A node with no children (also called an external node in some texts). |
| Internal node | A node that has at least one child (not a leaf). |
2) Size and levels
| Term | Meaning |
|---|---|
| Depth (of a node) | Number of edges on the path from the root to that node. The root has depth 0. |
| Level | Often used interchangeably with depth: “level k” = nodes at depth k (check your textbook for off-by-one variants). |
| Height (of a node) | Length of the longest path from that node down to a leaf (number of edges). Leaves have height 0 in this convention. |
| Height (of a tree) | Height of the root—the maximum depth of any leaf; or “number of levels minus 1,” depending on definition—stay consistent in code. |
| Degree (of a node) | Number of children of that node. In a binary tree, degree ≤ 2. |
| Size (subtree) | Number of nodes in a subtree (often computed recursively: 1 + sum(sizes of children)). |
3) Paths and subtrees
| Term | Meaning |
|---|---|
| Path | A sequence of distinct nodes where each consecutive pair is connected by an edge. In a tree there is exactly one simple path between any two nodes. |
| Ancestor | Any node on the path from the root down to a given node (including the root; sometimes the node itself is excluded—read carefully). |
| Descendant | Any node in the subtree rooted at a given node (children, grandchildren, etc.). |
| Subtree | A node together with all its descendants; it is itself a tree rooted at that node. |
| Forest | A collection of disjoint trees (no shared nodes). Removing the root from a tree often yields a forest of subtrees. |
4) Binary-tree vocabulary
These terms appear again in Tree types and binary-tree lessons.
| Term | Meaning |
|---|---|
| Binary tree | Each node has at most two children, often named left and right (order may matter for BSTs). |
| Left / right child | Designated children in a binary tree; a missing child is represented by NULL in C pointer implementations. |
| Full binary tree | Every node has 0 or 2 children (no node with exactly one child)—definition varies; confirm in your assignment. |
| Complete binary tree | All levels filled except possibly the last, filled left to right—ideal for array (heap) storage. |
| Perfect binary tree | All internal nodes have two children and all leaves at the same depth. |
Key takeaway
Use depth from the root down and height from a node down to leaves; keep one convention for “height of empty tree” (−1 vs 0) in your C functions. Binary-tree “full / complete / perfect” labels are not universal—match your problem statement.
Next up: Tree applications · Tree versus graph · Tree types