Tree Basics

Trees are hierarchical data structures that model parent–child relationships. They are a fundamental building block for:

Understanding tree terminology and properties is a prerequisite for binary trees, heaps, balanced trees, and many algorithms.

Definitions and Terminology

Node – a basic element of the tree (contains a value and references to children).
Root – the topmost node with no parent.
Parent / child – edges connect a parent to its children.
Leaf – a node with no children.
Sibling – nodes that share the same parent.
Subtree – a node together with all of its descendants.
Height of a node – the number of edges on the longest path down to a leaf.
Depth of a node – the number of edges from the root to the node.

Trees are acyclic (no cycles) and typically connected (one root, every node reachable).

General tree – each node can have any number of children.
Binary tree – each node has at most two children (left/right).
N‑ary tree – each node has at most N children.
Rooted tree – a designated root node (most data structure trees are rooted).

Later articles in this series focus on specific tree types used in algorithms.

Traversals define how we visit all nodes:

Preorder (root, then children):
- Visit node, then recursively traverse each child.
Postorder (children, then root):
- Traverse all children, then visit node.
Level order (BFS):
- Visit nodes level by level from top to bottom.

For binary trees, we also have inorder traversal:

Trees are natural when:

Data has a hierarchy (e.g. DOM, directories).
You need logarithmic operations by height (e.g. balanced BSTs, heaps).
You want to model combinatorial structures like expressions, parses, decision trees.

They also provide the backbone for many algorithms:

In later sections we will specialize this foundation into: