Tree (data structure)

A tree represents hierarchical relationships through nodes and edges, beginning at a root and branching toward descendants. Each node may have a parent, zero or more children, and a depth measured by its distance from the root; the tree’s height is the greatest node depth. A node with no children is a leaf, while an internal node has at least one child. In a rooted tree, every node except the root has exactly one parent, and there is exactly one path between any two connected nodes. This structure is acyclic: following child links can never return to an earlier node.¹

The word “tree” covers several related forms. A binary tree allows at most two children per node, whereas an m-ary tree allows up to m. A binary search tree adds an ordering rule: keys in the left subtree precede the node’s key, and keys in the right subtree follow it. That rule makes in-order traversal produce sorted output, but efficiency depends on height. A highly skewed tree can behave like a linked list, taking linear rather than logarithmic time for search.

Tree performance is governed chiefly by height and by the rules imposed on node placement. Traversals visit nodes in systematic orders: preorder processes a node before its children, postorder processes it afterward, and in-order traversal is especially useful for binary search trees. Breadth-first traversal visits nodes level by level, usually with a queue; depth-first traversal uses recursion or an explicit stack. Each traversal takes O(n) time when every node is visited once.

Balanced search trees constrain height so that lookup, insertion, and deletion remain logarithmic in the number of nodes. AVL trees maintain stricter height balance through rotations, while red-black trees use a looser color-based invariant and often require fewer structural adjustments. Heaps impose a parent-child priority rule and support efficient access to a minimum or maximum, but they are not general search trees. B-trees and related B+ trees store many keys per node, reducing disk accesses and making them central to databases and file systems.²³

Trees are useful whenever information is nested, ordered, or repeatedly divided into regions. File systems model directories as trees; compilers represent program structure with abstract syntax trees; and XML or HTML documents use tree-like document models. Databases use B-tree-family indexes to locate records while minimizing costly storage reads. Priority queues are commonly implemented with binary heaps, and network routing, artificial intelligence, and operations research use specialized trees for partitioning, decision-making, and state exploration.

Not every practical tree is explicitly stored as one node object per element. A trie indexes strings by shared prefixes and can provide lookup time proportional to key length rather than to the number of stored keys. Suffix trees and suffix arrays support pattern matching and text indexing, while spatial structures such as k-d trees and R-trees organize points, rectangles, or other geometric objects. These variants trade memory, update cost, ordering guarantees, and query type against one another rather than offering a universally best representation.⁴

Tree terminology also describes structures that are not strictly hierarchical in the everyday sense. An abstract syntax tree usually omits punctuation and other surface details, preserving the grammatical relationships needed for analysis or code generation. A Merkle tree stores cryptographic hashes at internal nodes, allowing a system to verify that a large data set or a portion of it has not changed without comparing every item. Merkle trees underpin integrity checks in distributed systems and versioned data structures.

Some trees are deliberately compressed or implicit. Patricia tries compress chains of single-child nodes, reducing space for sparse key sets. A heap may be represented compactly in an array because the children of the node at index i occupy predictable positions, avoiding explicit pointers. Trees can also be persistent: updates create new paths while sharing unchanged subtrees with earlier versions. This technique supports immutable collections, rollback, and historical queries, but shared structure makes memory ownership and update semantics more subtle.⁵

Ancestor

A node on the path from the root to another node, excluding that node itself.

Binary search tree

A binary tree whose node keys are ordered so that left-subtree keys precede and right-subtree keys follow the node key.

Height

The greatest distance, measured in edges, from the root to any node.

Leaf

A node with no children.

Rotation

A local restructuring operation used to preserve search-tree ordering while changing subtree heights.

Trie

A prefix tree that stores sequences by sharing paths for common prefixes.