Trees and Hierarchical Data
Trees model hierarchy. Their recursive shape lets a solution define a contract for one subtree, then combine child results at the parent.
Hierarchy Instead of Sequence
A tree organises data hierarchically. Each node holds a value and references to child nodes; every node has exactly one parent except the root, which has none. There are no cycles, and every node is reachable from the root by exactly one path.
That last property — one unique path to every node — is what distinguishes a tree from a general graph and what makes tree algorithms comparatively simple. There is never a question of which route to take, and no need for a visited set during traversal.
A counting fact follows immediately and is worth knowing: a tree with n nodes has exactly n − 1 edges. Each edge connects a node to its parent, every node has one parent, and only the root does not. Adding any further edge would create a cycle, which is why a tree is sometimes defined as a minimally connected graph — connected, but removing any edge disconnects it.
Trees fit data that is genuinely hierarchical: a filesystem where directories contain files and other directories, an HTML document where elements nest, an organisation chart, a family tree. Forcing such data into a flat sequence loses the containment relationship the structure is about.
They are also used where no hierarchy exists in the data at all, purely because a tree's shape makes searching fast. A binary search tree over a set of numbers imposes a hierarchy that nothing in the numbers requires — it exists so that halving the search space at each step becomes possible.
- One parent per node, one root, no cycles, one path to each node
- n nodes means exactly n − 1 edges
- Natural fit for filesystems, documents, and nested categories
- Also imposed artificially, purely to make searching logarithmic
The Vocabulary
Exam questions turn on these terms more often than on any algorithm, so precision here is worth more than it looks.
Root — the single node with no parent. Leaf (or external node) — a node with no children. Internal node — any node with at least one child. Siblings — nodes sharing a parent. Ancestors of a node are every node on the path up to the root; descendants are every node in its subtree. A node counts as both its own ancestor and its own descendant under the usual convention.
Degree of a node is its number of children. Degree of the tree is the maximum degree of any node in it — so a binary tree has degree 2. Note this differs from graph theory, where degree counts all incident edges including the one to the parent.
Depth of a node is the number of edges from the root down to it, making the root depth 0. Height of a node is the number of edges on the longest path from it down to a leaf, making every leaf height 0. The height of the tree is the height of its root. Depth and height run in opposite directions, and swapping them is the single most common vocabulary error.
A level is the set of all nodes at the same depth; level 0 contains only the root.
Both conventions exist for counting — some texts count nodes instead of edges, making a single-node tree height 1 rather than 0. Neither is wrong, but they differ by exactly one, so state which you are using. Under the edge convention an empty tree has height −1.
A subtree is any node together with all its descendants, and it is itself a tree. That recursive property is why almost every tree algorithm is written recursively: solving for a node means solving for its subtrees and combining.
- Degree of a node is its child count; of the tree, the maximum
- Depth measures down from the root; height measures down to a leaf
- Edge and node counting conventions differ by one — say which
- Every subtree is itself a tree, which is why recursion fits
Shape, Balance, and Why It Matters
Nearly every tree operation walks a path from the root toward a leaf, so its cost is proportional to the height — not to the number of nodes. This one fact motivates most of the machinery in the specialised trees below.
A tree of n nodes can have height anywhere from ⌊log₂ n⌋ to n − 1. The lower bound is achieved when every level is filled; the upper when every node has a single child, producing a degenerate tree that is a linked list with tree vocabulary. Its operations are O(n), and every advantage of the structure is gone.
Degeneracy is not a contrived worst case. Inserting already-sorted data into an unbalanced binary search tree produces exactly that chain, and sorted input is common. The failure is silent: the code is correct, small shuffled tests pass, and performance collapses on real data.
A balanced tree constrains height directly — the usual definition requires the two subtree heights at every node to differ by at most one. That guarantees O(log n) height and therefore O(log n) operations.
Several fill-related terms describe binary trees specifically and are routinely confused. A full tree has every node with 0 or 2 children, saying nothing about height. A complete tree has all levels filled except possibly the last, packed to the left — the property that lets a heap live in an array. A perfect tree has all internal nodes with 2 children and all leaves on one level, which implies both full and complete and gives exactly 2^(h+1) − 1 nodes.
Recursion depth follows height too, so a degenerate tree with a million nodes will overflow the call stack where a balanced one uses 20 frames.
| Shape | Height | Operations |
|---|---|---|
| Perfect or complete | ⌊log₂ n⌋ | O(log n) |
| Balanced (AVL, red-black) | O(log n) | O(log n) guaranteed |
| Random insertion order | ≈ 1.39 log₂ n expected | O(log n) expected |
| Degenerate | n − 1 | O(n) — no better than a list |
- Cost tracks height, not node count
- Sorted input into an unbalanced BST builds the worst case
- Full, complete and perfect describe fill; balanced constrains height
- Recursion depth is the height — degenerate trees overflow the stack
Terms, operations, and practical uses
Tree terminology
- RootThe only node with no parent.
- Parent and childTwo nodes connected by one downward edge.
- SiblingNodes that have the same parent.
- LeafA node with no children.
- SubtreeA node together with every descendant reachable below it.
Measurements and properties
- DepthThe number of edges from the root to a node.
- HeightThe longest downward edge count from a node to any leaf.
- DegreeThe number of children attached to a node.
- N − 1 edgesA connected tree with
Nnodes has exactlyN − 1edges and one unique path between any pair.
Tree families and uses
- Binary treeEach node has at most a left child and a right child.
- Binary search treeEvery subtree obeys an ordering rule, allowing one branch to be discarded during lookup.
- Balanced treeKeeps height proportional to
log Nso search, insertion, and removal do not degrade into a chain. - Hierarchical dataFile directories, document trees, organization charts, and syntax trees naturally use parent–child structure.
Read a binary search tree in sorted order
def inorder(node, answer):
if node is None:
return
inorder(node.left, answer)
answer.append(node.value)
inorder(node.right, answer)
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
root = Node(8, Node(3, Node(1), Node(6)), Node(10))
result = []
inorder(root, result)
print(*result)#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {
}
};
void inorder(TreeNode* node, vector<int>& answer) {
if (node == nullptr) return;
inorder(node->left, answer);
answer.push_back(node->val);
inorder(node->right, answer);
}
int main() {
TreeNode* root = new TreeNode(8, new TreeNode(3, new TreeNode(1), new TreeNode(6)), new TreeNode(10));
vector<int> answer;
inorder(root, answer);
for(size_t i = 0; i < answer.size(); i++) {
if (i) cout << ' ';
cout << answer[i];
}
cout << '\n';
}import java.util.*;
public class Main {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
void inorder(TreeNode node, List<Integer> answer) {
if (node == null) return;
inorder(node.left, answer);
answer.add(node.val);
inorder(node.right, answer);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(8, new TreeNode(3, new TreeNode(1), new TreeNode(6)), new TreeNode(10));
List<Integer> answer = new ArrayList<>();
new Main().inorder(root, answer);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < answer.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(answer.get(i));
}
System.out.println(sb);
}
}Step through it
Running on BST containing 8, 3, 10, 1, 6
Read all 17 Steps
- Call inorder(8) The root call begins at 8. Inorder must finish the complete left subtree before it can record 8.
- Descend to 3 8 has a left child, so call inorder(3). Only 3 is the current node; 8 remains on the suspended call stack.
- Descend to 1 The left child of 3 is 1, so call inorder(1). Nothing has been appended yet.
- Check 1.left The left child of 1 is null. That base-case call returns immediately without changing the output.
- Visit 1 The left subtree of 1 is complete, so append 1. This is the first actual visit event.
- Check 1.right The right child of 1 is also null. Its base case returns, completing inorder(1).
- Return to 3 Control returns to the suspended inorder(3) call after its entire left subtree has finished.
- Visit 3 Append 3 between its left and right subtree calls. The output is now 1 3.
- Descend to 6 Now call inorder(6), the right subtree of 3. Notice that 6 is still inside 8's left subtree.
- Check 6.left 6 has no left child, so the null base case returns without appending a value.
- Visit 6 Append 6 after its empty left subtree and before its empty right subtree.
- Return through 3 6.right is null, so inorder(6) returns. The call for 3 has now completed both subtrees and also returns.
- Visit 8 The complete left subtree of 8 is finished. Append the root value 8.
- Descend to 10 Call inorder(10), the right subtree of the root. It is the only remaining subtree.
- Check 10.left 10.left is null, so return to the inorder(10) call without changing the output.
- Visit 10 Append 10. Its right child is null as well, so the traversal has no nodes left to process.
- Traversal complete Every node was appended exactly after its left subtree and before its right subtree. The resulting order is sorted.
The Specialised Trees
Each named tree exists because it makes one particular query cheap. Recognising which query a problem needs is how you choose between them.
A binary search tree stores keys so that everything in the left subtree is smaller and everything in the right is larger. That invariant makes search, insertion, and deletion O(h), and makes in-order traversal emit the keys in sorted order — the property hash tables cannot offer.
AVL and red-black trees are binary search trees that repair their own balance after every modification using rotations, small local rearrangements that change shape while preserving the ordering. AVL keeps subtree heights within one and so stays shorter, favouring lookup-heavy use. Red-black enforces a looser colour invariant that bounds height at 2·log₂(n+1) and rebalances less, favouring modification-heavy use — which is why standard library maps and sets usually choose it.
B-trees widen instead of deepening: each node holds many keys and has many children, so the tree is only a few levels deep even for millions of records. This matters when a node lives on disk and each level costs a disk read, which is why databases and filesystems use B-trees and B+ trees rather than binary ones.
Heaps order by priority rather than by key: every parent compares favourably to its children, so the minimum or maximum is always at the root, available in O(1). They are stored as complete trees inside arrays with no pointers, and they back priority queues and heap sort. A heap cannot search efficiently — that is the trade for O(1) access to the extreme.
Tries key by prefix rather than by comparison. A path from the root spells a string, so lookup is O(length of the key) independent of how many keys are stored, and every word sharing a prefix shares that path — which is what makes autocomplete work.
Segment trees and Fenwick trees store aggregates over ranges, answering 'sum of this range' and applying point updates in O(log n), where a prefix-sum array would need O(n) to absorb an update.
- BST for ordered keys; AVL and red-black to keep it balanced
- B-trees widen to cut disk reads — databases and filesystems
- Heaps give O(1) access to the extreme but cannot search
- Tries key by prefix; segment and Fenwick trees answer range queries