Tree Terminology

What Is a Tree?

A tree is a hierarchical data structure composed of nodes connected by edges. It models relationships where each item (node) may reference multiple sub-items (children), but cycles are not allowed. In computer science, we most often work with rooted trees, where one distinguished node is called the root and all edges conceptually point away from it.

Core Components and Relationships

Node

A fundamental element containing a value (or key) and references to zero or more children.

Edge

A connection between a node and one of its children.

Root

The topmost node of a rooted tree; it has no parent.

Parent

A node that has one or more children.

Child

A node directly connected and one level below a parent.

Leaf (External Node)

A node with no children.

Internal Node

A non-leaf node; it has at least one child.

Sibling

Nodes that share the same parent.

Ancestor

Any node on the path from the root to a given node (including the node itself by some conventions).

Descendant

Any node in the subtree rooted at a given node (including the node itself by some conventions).

Subtree

A node together with all of its descendants.

Forest

A collection of one or more disjoint trees.

Path

A sequence of nodes connected by edges, usually directed from ancestor to descendant in rooted trees.

Lowest Common Ancestor (LCA)

The deepest node that is an ancestor of two given nodes.

Structural Measures

Degree (of a node)

The number of children of a node.

Arity / Branching Factor

The fixed or maximum number of children per node in a class of trees (e.g., binary trees have arity 2). Branching factor can also refer to the average or observed number of children per node.

Depth (of a node)

The number of edges from the root to the node. The root has depth 0.

Level

Often defined as depth + 1; the root is at level 1 by this convention.

Height (of a node)

The number of edges on the longest downward path from the node to a leaf.

Height (of a tree)

The height of its root. Conventions vary for the empty tree: height may be defined as −1 or 0.

Size

The number of nodes in the tree (or in a subtree).

Width

The number of nodes at a given level; the maximum width is the maximum of these values over all levels.

Balance

A measure of how evenly subtree heights or sizes are distributed. Specific definitions vary by tree type (e.g., AVL, Red-Black).

Common Tree Classifications

Ordered vs. Unordered

In ordered trees, children have a defined sequence (e.g., left vs. right). In unordered trees, sibling order is irrelevant.

k-ary Tree

Each node has at most k children. A binary tree is a 2-ary tree.

Full (Proper) Binary Tree

Every node has either 0 or 2 children.

Complete Binary Tree

All levels are completely filled except possibly the last, which is filled from left to right without gaps.

Perfect Binary Tree

All internal nodes have exactly 2 children and all leaves are at the same depth.

Balanced Trees

Trees that enforce constraints to keep height logarithmic in the number of nodes (e.g., AVL trees, Red-Black trees, B-Trees).

Traversal Terminology

Traversals visit nodes in a defined order. Common traversal names and orders are:

• Preorder (DFS): Visit node, then recursively traverse its children (for binary trees: node, left, right).
• Inorder (DFS, binary trees): Traverse left subtree, visit node, traverse right subtree. Useful for retrieving sorted keys from a Binary Search Tree.
• Postorder (DFS): Recursively traverse children, then visit node.
• Level-order (BFS): Visit nodes level by level from the root downward, typically using a queue.

Implementation Notes

• Pointer/Reference-based: Each node stores references to its children (and optionally its parent). Flexible and general-purpose.
• Array-based: Effective for complete binary trees (e.g., heaps). Given index i, children may be at 2i+1 and 2i+2, and the parent at floor((i−1)/2).

Conventions and Pitfalls

• Be explicit about whether height of an empty tree is −1 or 0, and whether depth of the root is 0 or 1 (level vs depth).
• Distinguish between ordered sibling positions (e.g., left/right) and unordered sets of children.
• Balance can mean different things depending on the tree variant (height-balanced vs. color/black-height constraints).
• Terminology like degree can refer to a single node’s number of children or, less commonly, the maximum degree over the tree.

Why Terminology Matters

Precise terms enable clear reasoning about correctness, complexity, and implementation choices. Mastering these definitions is essential before studying specific tree types and algorithms.

Next Topic