A tree is a hierarchical data structure made of nodes connected by parent-child edges, with a single root node at the top and exactly one path between any two nodes. Every node except the root has one parent, any node may have children, and nodes without children are called leaves.
Among data structures in programming, a tree sits between the linear structures, such as the array, the linked list, the stack and the queue, and the fully general graph. Formally, a tree is a connected graph without cycles, which is why a tree with n nodes always has exactly n minus 1 edges. That restriction makes trees ideal for representing hierarchies and for keeping data ordered for fast search.
Structure and terminology of a tree
A tree is described with a small, precise vocabulary that recurs in every algorithm built on it. Knowing these terms is essential, because performance guarantees are usually stated in terms of height, not in terms of the number of nodes.
| Term | Definition | Why it matters |
|---|---|---|
| Root | The only node without a parent | Starting point of every traversal |
| Leaf | A node without children | Ends of search paths |
| Depth of a node | Number of edges from the root to the node | Cost of reaching that node |
| Height of a tree | Largest depth of any leaf | Worst-case cost of search and insert |
| Subtree | A node together with all its descendants | Basis of recursive algorithms |
| Degree or branching factor | Number of children of a node | Shapes height for a given size |
In memory, a tree is usually stored as nodes holding references to their children, much like a linked list with several next pointers. A complete binary tree can instead be stored compactly in an array, where the children of the node at index i sit at indexes 2i + 1 and 2i + 2. Binary heaps use exactly this layout.
Types of trees and what they are used for
The word tree covers a whole family of structures. They share the hierarchical shape but differ in the rules about order, branching and balance, and those rules decide what each type does well.
| Type | Defining rule | Typical use |
|---|---|---|
| Binary tree | Each node has at most two children | Expression trees, base for others |
| Binary search tree | Left keys smaller, right keys larger | Ordered sets and maps |
| AVL and red-black trees | Self-balancing binary search trees | Standard library ordered maps |
| B-tree and B+ tree | Many keys per node, all leaves on one level | Database and file system indexes |
| Heap | Parent ordered against its children | Priority queues, heap sort |
| Trie | Edges labeled with characters | Autocomplete, prefix search, routing |
| General n-ary tree | Any number of children | File systems, the DOM, syntax trees |
B-trees illustrate how hardware shapes the choice. Because a disk or SSD reads data in pages, a B-tree stores hundreds of keys in one node, so even billions of records are reachable within a handful of page reads. Binary trees would need far more levels and far more reads for the same data.
Traversal and operations
Visiting every node of a tree is called traversal, and the visiting order determines what the result means. Depth-first traversal follows one branch to its leaves before backtracking, and is naturally expressed with recursion or an explicit stack. Breadth-first traversal visits the tree level by level with a queue.
For binary trees, depth-first traversal has three standard orders. In-order traversal of a binary search tree returns the keys in sorted order, which is why such trees double as sorting structures.
- Pre-order visits a node before its children, which suits copying a tree or serializing it.
- In-order visits the left subtree, the node, then the right subtree, which yields sorted keys.
- Post-order visits children before the node, which suits deleting a tree or evaluating expressions.
- Level-order visits nodes by depth, which suits finding the shortest path from the root.
The cost of search, insertion and deletion depends on the height. In a balanced tree the height grows with log2 of n, so a million keys need only about 20 levels. In a degenerate tree, where every node has one child, the height equals n and the tree behaves like a slow linked list.
Trees compared with other data structures
Choosing a tree is usually a decision against a hash table, a sorted array or a general graph. The main advantage of a search tree is ordered access together with efficient updates, which neither hash tables nor sorted arrays provide at the same time.
| Operation or property | Balanced search tree | Hash table | Sorted array |
|---|---|---|---|
| Lookup by key | O(log n) | O(1) on average | O(log n) |
| Insert or delete | O(log n) | O(1) on average | O(n) |
| Ordered iteration | Yes, in-order | No | Yes |
| Range queries | Efficient | Not supported | Efficient |
| Worst case | Guaranteed if balanced | O(n) with many collisions | Predictable |
Compared with a graph, a tree forbids cycles and multiple parents. When data allows one item to belong to several parents, such as a file with hard links or a person in several departments, a graph or a directed acyclic graph is the correct model.
Common mistakes when working with trees
Most tree bugs stem from unbalanced growth, unbounded recursion or confusing a tree with a graph. Inserting already sorted keys into a plain binary search tree is the classic trap: every new key becomes the right child of the previous one, and the tree degenerates into a list.
| Problem | Symptom | Remedy |
|---|---|---|
| Degenerate search tree | Lookups slow down to linear time | Use a self-balancing tree |
| Deep recursion | Stack overflow on large inputs | Traverse with an explicit stack |
| Hidden cycles | Traversal never ends | Validate input or track visited nodes |
| Stale parent pointers | Corrupted structure after deletion | Update parent and child links together |
A non-technical view
A tree in programming is a way of organizing information as a family tree or a company chart, only drawn upside down. There is one item at the top. It branches into items below it, and those branch further.
The folders on your computer form a tree. One main folder holds other folders, which hold more folders and files. Because everything has exactly one place, finding an item means following one path from the top. You never have to search everything.
A concrete example
An online bookshop stores about five million orders and must show a customer all orders placed between two dates within a fraction of a second. Scanning every order for each request would be far too slow.
The database therefore keeps a B+ tree index on the order date. Each index node holds several hundred dates, so the tree is only three or four levels deep. A query descends from the root to the first matching leaf, then walks along the linked leaves until it passes the end date.
The query reads only a few index pages plus the matching orders, and it returns the results already sorted by date. Adding new orders keeps the tree balanced automatically, so response times stay stable as the shop grows.