Tree Terminology - PCCST303

Arrays and linked lists arrange elements in a single sequence, one after another:

0123

HEAD

↓

NULL

datanext

Many real problems are not sequences at all. A file system, an org chart, a family tree: each of these branches, one item having several items "below" it. That shape is a tree.

Tree

Definition

A tree is a non-linear data structure that represents hierarchical relationships between elements, a top item connected to zero or more items below it, each of which can itself have items below it.

Vocabulary

Every tree term below refers to the small tree used throughout this page:

Node — each item in the tree, e.g. A, B, D.
Root — the topmost node, the only node with no parent. Here, A.

Parent — the node directly above a given node. A is the parent of B and C:

Child — a node directly below a parent. D and E are children of B:

Siblings — nodes sharing the same parent. B and C are siblings; so are D and E:

Leaf — a node with no children. Here, D, E, and F:

Internal node — a node with at least one child. Here, A, B, and C:

Degree of a node — the number of children it has:

degree(A) = 2

degree(C) = 1

degree(D) = 0

Edge — a connection between two nodes, e.g. the link from A to B:

Path — a sequence of connected nodes, e.g. A → B → E:

Depth and height

Key Idea

Depth of a node is the number of edges from the root down to that node. Height of a node is the number of edges on the longest downward path from that node to a leaf. The height of the whole tree is the height of its root.

With root depth 0:

depth(A) = 0
depth(B) = depth(C) = 1
depth(D) = depth(E) = depth(F) = 2

Depth counts down from the root; height counts up from the leaves. A sits at depth 0, and the longest path from A down to a leaf (A → B → D, or A → B → E) has 2 edges, so:

height(A) = 2
height(B) = height(C) = 1
height(D) = height(E) = height(F) = 0

Every leaf has height 0 by definition, there's no path to go further down.

Some textbooks measure height and depth in nodes rather than edges, giving values one higher. In an exam, follow whichever convention the question implies, and state your convention if it's ambiguous.

Why trees, and why binary trees specifically

A tree with no restriction on the number of children per node is a general tree. A binary tree restricts every node to at most two children, conventionally distinguished as the left child and the right child, covered in detail, with its types and properties, in Binary Tree Types and Properties.

Module 3 focuses on binary trees because restricting each node to at most two children gives us a simple structure that can support important data structures and representations, including binary search trees (BSTs), heaps, and expression trees. The two-child structure also keeps tree traversal and implementation relatively straightforward.

Quick recall

A tree represents hierarchy; a node with no parent is the root, a node with no children is a leaf.
Depth is measured down from the root (root at depth 0); height is measured up from the leaves (a leaf has height 0).
Degree of a node = number of its children; siblings share a parent; a path is a sequence of connected nodes.
Whether height/depth is counted in edges or nodes is a convention, watch which one a question expects.