Tree Basics & Terminology
Trees Are Non-Linear
Every data structure you have seen so far — arrays, linked lists, stacks, queues — stores data in a linear sequence. Elements follow one after another in a single line.
LINEAR structures — one path through the data: Array: [10] → [20] → [30] → [40] → [50] Linked list: 10 → 20 → 30 → 40 → 50 Stack: (top) 30 | 20 | 10 (bottom)
A tree is different. Data is organised in a hierarchy — each element can connect to multiple elements below it, creating a branching structure with no single line through it.
NON-LINEAR — a tree:
10
/ \
20 30
/ \ \
40 50 60
\
70
Multiple paths exist from the top to the bottom.
No single sequence captures the full structure.
10 connects to both 20 and 30 simultaneously.
Trees model real-world hierarchies naturally: file systems, organisation charts, HTML document structure, game state spaces, and decision trees all have this branching, parent-child structure that linear data structures cannot represent cleanly.
The Reference Tree
Every term in this page will be explained using this single labelled tree. Study its shape before reading the definitions.
A ← Level 0
/ | \
B C D ← Level 1
/\ |
E F G ← Level 2
/ / \
H I J ← Level 3
Nodes: A, B, C, D, E, F, G, H, I, J Edges: A-B, A-C, A-D, B-E, B-F, D-G, E-H, G-I, G-J
Node
A node is the fundamental unit of a tree. Every piece of data stored in a tree lives inside a node. A node contains:
┌──────────────────────────────────┐ │ NODE │ │ ┌────────┐ │ │ │ data │ ← the stored value │ │ └────────┘ │ │ ┌────────┐ ┌────────┐ │ │ │ child1 │ │ child2 │ ... │ ← references to children │ └────────┘ └────────┘ │ └──────────────────────────────────┘
In the reference tree, every labelled letter (A through J) is a node. The tree has 10 nodes.
All nodes: A B C D E F G H I J
↑
each is one node
Root
The root is the single topmost node of the tree. It is the only node with no parent. Every tree has exactly one root. All other nodes descend from the root.
A ← ROOT (no parent, topmost)
/ | \
B C D
/\ |
E F G
/ / \
H I J
Properties of the root:
✓ Has no parent
✓ Exactly one root per tree
✓ Every other node is reachable from the root
✓ Depth of root = 0
In the reference tree, A is the root.
Edge
An edge is a connection between a parent node and a child node. It represents the relationship "parent has child".
A
/|\
/ | \
Edge A→B / | \ Edge A→D
B | D
Edge A→C
C
A tree with n nodes has exactly n-1 edges.
10 nodes → 9 edges in our reference tree.
Edges in the reference tree: A-B, A-C, A-D, B-E, B-F, D-G, E-H, G-I, G-J — that is 9 edges.
Parent and Child
A parent is a node that has one or more nodes directly below it. Those nodes below it are its children. This is always a direct one-level relationship — no skipping levels.
A
/ | \
B C D A is parent of B, C, D
/\ | B and C and D are children of A
E F G
/ / \
H I J D is parent of G
G is child of D
EVERY node (except root) has exactly ONE parent.
A node can have ZERO or MORE children.
Parent-child pairs in reference tree:
A → {B, C, D} (A is parent of B, C, D)
B → {E, F} (B is parent of E, F)
D → {G} (D is parent of G)
E → {H} (E is parent of H)
G → {I, J} (G is parent of I, J)
C, F, H, I, J have no children.
Leaf Node
A leaf node (also called a terminal node or external node) is a node with no children. It sits at the boundary of the tree — the end of every branch.
A
/ | \
B C* D C is a leaf
/\ |
E F* G F is a leaf
/ / \
H* I* J* H, I, J are leaves
Leaves marked with *: C, F, H, I, J
In the reference tree, C, F, H, I, J are leaf nodes — they have no children.
An internal node (also called a non-leaf node) is any node that has at least one child. In the reference tree, A, B, D, E, G are internal nodes.
INTERNAL nodes (have at least one child): A, B, D, E, G LEAF nodes (have zero children): C, F, H, I, J
Sibling
Siblings are nodes that share the same parent. They are at the same level under the same parent.
A
/ | \
B C D B, C, D are siblings (all children of A)
/\ |
E F G E and F are siblings (both children of B)
/ / \
H I J I and J are siblings (both children of G)
H has no siblings (only child of E)
Sibling groups in reference tree:
{B, C, D} — children of A
{E, F} — children of B
{I, J} — children of G
{G} — only child of D (no siblings)
{H} — only child of E (no siblings)
Note: C is a sibling of B and D — they share parent A — even though C has no children of its own.
Ancestor and Descendant
Ancestor: any node on the path from the root to a given node (not including the node itself). A parent is the immediate ancestor. A parent's parent is also an ancestor.
Descendant: any node reachable by following child edges from a given node. A child is the immediate descendant. A child's child is also a descendant.
A
/ | \
B C D
/\ |
E F G
/ / \
H I J
Ancestors of H: E → B → A (path from root to H, excluding H)
Ancestors of I: G → D → A (path from root to I, excluding I)
Ancestors of G: D → A
Descendants of A: B, C, D, E, F, G, H, I, J (all other nodes)
Descendants of B: E, F, H (everything under B)
Descendants of D: G, I, J
Descendants of E: H
Descendants of C: none (C is a leaf)
RULE: X is an ancestor of Y ↔ Y is a descendant of X X is the parent of Y ↔ Y is a child of X (parent/child = direct; ancestor/descendant = any number of levels)
Subtree
A subtree is a node together with all of its descendants. Every node in a tree is the root of its own subtree. Removing a node from the tree (along with all edges to its children) creates one or more smaller subtrees.
A Full tree
/ | \
B C D
/\ |
E F G
/ / \
H I J
Subtree rooted at B: Subtree rooted at D:
B D
/\ |
E F G
/ / \
H I J
Subtree rooted at G: Subtree rooted at E:
G E
/ \ |
I J H
Subtrees rooted at leaves (C, F, H, I, J):
Each is a single node — the smallest possible subtree.
Key property: Every subtree is itself a valid tree. This is why recursive algorithms work so naturally on trees — processing a tree is the same as processing its root, then processing each of its subtrees.
Depth of a Node
The depth of a node is the number of edges on the path from the root down to that node.
Depth is measured TOP-DOWN (from root):
A depth 0 ← root is always depth 0
/ | \
B C D depth 1
/\ |
E F G depth 2
/ / \
H I J depth 3
Depth formula:
depth(root) = 0
depth(node) = depth(parent) + 1
Node depths in reference tree: A → depth 0 B, C, D → depth 1 E, F, G → depth 2 H, I, J → depth 3
Height of a Node
The height of a node is the number of edges on the longest path from that node down to any leaf in its subtree.
Height is measured BOTTOM-UP (from leaves):
A height 3 ← longest path: A→B→E→H (3 edges)
/ | \
B C D B:height 2, C:height 0, D:height 2
/\ |
E F G E:height 1, F:height 0, G:height 1
/ / \
H I J H,I,J: height 0 (leaves)
Height formula:
height(leaf) = 0
height(node) = 1 + max(height(children))
Node heights in reference tree: H, I, J, C, F → height 0 (all leaves) E → height 1 (one edge to leaf H) G → height 1 (one edge to leaf I or J) B → height 2 (E→H is two edges below B) D → height 2 (G→I or G→J is two edges below D) A → height 3 (B→E→H is three edges below A)
Height of the Tree
The height of the tree = the height of the root = the length of the longest root-to-leaf path.
Height of reference tree = height of A = 3 Longest path: A → B → E → H (3 edges) Also valid: A → D → G → I (3 edges)
Level
The level of a node is its depth + 1 in some conventions, or simply its depth in others. Most modern definitions use level = depth (root at level 0). Some older texts use root at level 1 — always check which convention is being used.
Using level = depth (root at level 0): Level 0: A Level 1: B C D Level 2: E F G Level 3: H I J Number of nodes at each level: Level 0: 1 node (A) Level 1: 3 nodes (B, C, D) Level 2: 3 nodes (E, F, G) Level 3: 3 nodes (H, I, J)
Level of a node = number of nodes on the path from root to that node, inclusive.
Degree of a Node
The degree of a node is the number of children it has.
A degree 3 (children: B, C, D)
/ | \
B C D B:degree 2, C:degree 0, D:degree 1
/\ |
E F G E:degree 1, F:degree 0, G:degree 2
/ / \
H I J H,I,J: degree 0
Degree of a LEAF = 0 (no children).
Degree of the TREE = maximum degree among all nodes = 3 (node A).
Degree table for reference tree: Node A: degree 3 Node B: degree 2 Node D: degree 1 Node E: degree 1 Node G: degree 2 Nodes C, F, H, I, J: degree 0 (leaves) Degree of the tree: 3 (highest node degree)
Path
A path is a sequence of nodes where each consecutive pair is connected by an edge. In a tree, there is exactly one unique path between any two nodes.
A
/ | \
B C D
/\ |
E F G
/ / \
H I J
Path from A to H: A → B → E → H (3 edges, length 3)
Path from A to J: A → D → G → J (3 edges, length 3)
Path from B to G: B → A → D → G (3 edges, must go up through A)
Path from H to I: H → E → B → A → D → G → I (6 edges)
UNIQUENESS: there is exactly ONE path between any two nodes in a tree.
This is one of the properties that DEFINES a tree.
Length of a path = number of edges in the path.
Complete Terminology Reference
Reference tree:
A
/ | \
B C D
/\ |
E F G
/ / \
H I J
TERM DEFINITION IN REFERENCE TREE
──────────────────────────────────────────────────────────────────────────
Node Basic unit storing data A,B,C,D,E,F,G,H,I,J
Root Only node with no parent A
Leaf / Terminal Node with no children C, F, H, I, J
Internal node Node with at least one child A, B, D, E, G
Edge Connection between parent and child 9 edges total
Parent Direct node above A is parent of B,C,D
Child Direct node(s) below B,C,D are children of A
Sibling Nodes sharing the same parent B,C,D are siblings
Ancestor Any node on path from root to node A,B,E are ancestors of H
Descendant Any node reachable downward B,E,F,H are descendants of B
(wait — F is child of B ✓)
Subtree Node plus all its descendants Subtree at B: {B,E,F,H}
Depth of node Edges from root to node depth(H)=3, depth(G)=2
Height of node Edges from node to deepest leaf height(B)=2, height(I)=0
Height of tree Height of root 3
Level Same as depth (root=0) A:0, B:1, E:2, H:3
Degree of node Number of children degree(A)=3, degree(G)=2
Degree of tree Max degree among all nodes 3 (node A)
Path Sequence of nodes via edges A→B→E→H
Path length Number of edges in path length(A→H) = 3
Key Properties of Every Tree
For a tree with n nodes:
1. Exactly ONE root
Every tree has exactly one topmost node with no parent.
2. Exactly n-1 edges
Every node except the root has exactly one parent → one incoming edge.
n nodes, n-1 incoming edges total.
3. Exactly ONE path between any two nodes
No cycles. No alternate routes. One unique path only.
4. Removing any edge disconnects the tree
Every edge is essential — the tree is "minimally connected".
5. Every node is the root of a subtree
Recursion works naturally on trees because every subtree
is itself a valid tree.
Reference tree verification:
n = 10 nodes
edges = 9 = n-1 ✓
unique path between any two nodes ✓
one root (A) ✓
Common Mistakes
Confusing depth and height. Depth is measured top-down from the root (root has depth 0). Height is measured bottom-up from the leaves (leaves have height 0). The height of the tree equals the height of the root, which equals the maximum depth of any leaf. These two directions are opposite.
Saying "ancestor" when "parent" is meant, and vice versa. Parent is the immediate one-level relationship only. Ancestor covers any number of levels upward. A's parent is B (one edge). A's ancestors include B, B's parent, B's grandparent, all the way to the root.
Counting edges instead of nodes (or vice versa) when stating depth. Depth of a node is the number of edges from root to that node — not nodes. The root has depth 0 (zero edges from itself to itself). Its children have depth 1 (one edge).
Assuming every node has at most two children. A general tree has no restriction on the number of children. A node can have 0, 1, 2, or any number of children. The reference tree has a node (A) with 3 children. The restriction "at most 2 children" applies only to a specific category of tree — not all trees.
Summary
A tree is a non-linear, hierarchical data structure. Unlike linear structures that form a single chain, a tree branches — each node can connect to multiple children, creating a parent-child hierarchy.
Nine essential terms:
- ›Root — the one topmost node, no parent
- ›Leaf — a terminal node, no children (degree = 0)
- ›Internal node — any node with at least one child
- ›Edge — connection between parent and child; a tree with n nodes has n-1 edges
- ›Parent / Child — direct one-level relationship
- ›Sibling — nodes sharing the same parent
- ›Ancestor / Descendant — any-level upward / downward relationship
- ›Subtree — a node plus all its descendants; itself a valid tree
- ›Depth — edges from root DOWN to node (root = 0)
- ›Height — edges from node DOWN to deepest leaf (leaves = 0); tree height = root height
- ›Level — same as depth; nodes at the same level are equidistant from the root
- ›Degree — number of children; tree degree = maximum node degree
Key numeric properties for a tree with n nodes:
- ›Exactly n-1 edges
- ›Exactly one root
- ›Exactly one path between any two nodes
In the next topic, you will explore the different Types of Trees — binary trees, complete trees, perfect trees, balanced trees, and more — each defined by constraints on the degree or structure of nodes.
What makes a tree a non-linear data structure?