A tree is a non-linear data structure that represents hierarchical relationships. It’s a collection of nodes connected by edges such that each node (except one designated root) has exactly one parent, and there are no cycles. Children point downward; data flows from root to leaves.
Trees model anything with a parent/child relationship: family genealogies, file systems, organization charts, expression parsing, decision logic. The recursive structure (a tree is a root with sub-trees as children, each itself a tree) makes recursion the natural way to operate on them.
Anatomy
- Node: a single element holding data and pointers to its children.
- Root: the topmost node. Has no parent.
- Leaf: a node with no children.
- Internal node: a node that’s not a leaf (has at least one child).
- Edge: the connection between a parent and child, drawn as a line, implemented as a pointer.
- Path: a sequence of nodes from one ancestor down to a descendant. Exactly one path exists from the root to any node.
- Subtree: a node and all of its descendants — itself a tree.
Sample tree structures:
An expression tree representing . Internal nodes are operators; leaves are operands. Evaluating the tree (in postfix-traversal order) computes the expression.
A decision tree for classifying animals. Each internal node asks a yes/no question; each branch is the answer; each leaf is a final classification.
Measurements
- Height of a node: number of edges on the longest path from that node down to a leaf. Height of a leaf is 0; height of the tree is the height of the root.
- Depth of a node: number of edges from the root to that node. Depth of the root is 0.
- Level of a node: depth + 1. Root is level 1, its children are level 2, etc.
For a tree with height , the maximum number of nodes depends on the maximum branching factor:
- Binary tree (max 2 children per node): up to nodes — a perfect tree.
- General -ary tree (max children per node): up to nodes.
The formula is the binary special case. Don’t apply it to general trees with arbitrary branching.
Implementation
For a binary tree (each node has at most two children):
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node *newNode(int data) {
node *nptr = (node *) malloc(sizeof(node));
nptr->data = data;
nptr->left = NULL;
nptr->right = NULL;
return nptr;
}For a tree where nodes can have arbitrary numbers of children, you’d use a list or array of children instead of fixed left/right.
Types of trees
- Binary tree: each node has at most 2 children.
- Full binary tree: every node has either 0 or 2 children (no node with just one child).
- Complete binary tree: every level except possibly the last is fully filled; the last level fills left to right. (See heaps — they’re complete binary trees.)
- Binary search tree: a binary tree with the BST ordering invariant.
- AVL tree: a self-balancing BST.
- Red-black tree: another self-balancing BST.
Operations
The core tree operations:
- Traversal: visit every node. See Binary tree traversal for the four standard orders.
- Search: find a node containing a specific value.
- Insert: add a new node, possibly maintaining a structural invariant (e.g., BST order, AVL balance).
- Delete: remove a node and reorganize as needed.
The trick: trees are recursive by nature. An operation on a tree is typically the same operation applied to subtrees, plus some local work at the current node. See Recursion for why this matches.
Why trees matter
Trees are the dominant data structure when you need:
- Hierarchy: file systems, DOM trees, scene graphs, organization structures.
- Ordered storage with fast lookup: BSTs and balanced variants give search/insert/delete.
- Priority access: heaps for priority queues.
- Decision making: classification, expression parsing.
For balanced search trees and their variants, see Binary search tree, AVL tree, Red-black tree. For heap-style priority access, see Heap (data structure). For graph-style generalizations (where nodes can have multiple parents), see Graph.