Tree (data structure)

A tree is a non-linear structure for hierarchical relationships: nodes connected by edges where every 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 $32 \cdot 14 + (- 5) + 12$ . 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 $h$ , the maximum number of nodes depends on the maximum branching factor:

Binary tree (max 2 children per node): up to $2^{h + 1} - 1$ nodes — a perfect tree.
General $m$ -ary tree (max $m$ children per node): up to $\frac{m ^{h + 1} - 1}{m - 1}$ nodes.

The $2^{h + 1} - 1$ 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

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.

Where trees show up

Reach for a tree when you need:

Hierarchy: file systems, DOM trees, scene graphs, organization structures.
Ordered storage with fast lookup: BSTs and balanced variants give $O (lo g n)$ search/insert/delete.
Priority access: heaps for priority queues.
Decision making: classification, expression parsing.

Generalize the other way and you get a Graph, where nodes can have multiple parents.

Idriss Rami — Notes

Explorer