Tree terminology and rules

Trees are non-linear structures that express hierarchical relationships. A rooted tree has a distinguished root. Every other node has exactly one parent; each edge connects two nodes, and there is exactly one simple path between any two nodes in a tree. Unlike general graphs, trees contain no cycles.

Explore tree terminology interactively

Choose a term to highlight the relevant nodes or edges.

Highlight a term

The whole treeRoot nodeEdgesNodesLeaf nodesChild nodesParent nodesTree height (h = 2)Tree size (n = 10)

Test your understanding

What do B, D, E, F, G, H and I have in common?

Root nodesLeaf nodesParent nodesSibling nodes

Check answerReveal explanationNext question

Choose a term on the left and inspect the highlighted part of the example. Here R is the root, R, A and C are parent nodes, and B, D, E, F, G, H and I are leaves. The diagram is a general tree, not a binary tree, because R has three children and C has four.

How depth, height and size differ

• Depth of a node: number of edges from the root to that node. R has depth 0; D has depth 2.
• Height of a node: number of edges on its longest downward path to a leaf. A leaf has height 0.
• Height of the tree: height of its root, or maximum depth among the leaves. Here it is 2 edges.
• Size: total number of nodes, 10 here. A finite tree with 10 nodes has exactly 9 edges.
• Subtree: a node and all its descendants. The subtree rooted at A includes A, D and E.

Some sources count levels beginning at 1 rather than depth beginning at 0, and some define height by numbers of nodes rather than edges. State the convention rather than silently switching it.

Tree relationships and practical uses

Siblings share a parent, for example D and E. Ancestors of D include A and R; descendants of C include F, G, H and I. Real uses include scene hierarchies, menus, folder structures, parse trees and decision trees. A hierarchy is tree-shaped only if it respects the single-parent and no-cycle rules.

Check your understanding

Use the exercises in the visualizer. Predict which nodes will be highlighted for parents, leaves and tree height. Then try explaining why a tree with n nodes has n - 1 edges. You can prove the last fact by adding one non-root node at a time: each new node needs exactly one connecting edge.

Continue learning

Tree properties · Binary trees · Traversal

Reference: W3Schools tree terminology. The visualizer and exercise here are original implementations.