Trees and Graphs
Learning Objectives
By the end of this page, you should be able to:
- Define tree terminology: root, node, leaf, parent, child, depth, height, and subtree.
- Distinguish a binary tree from a binary search tree (BST) and state the BST search-order property.
- Implement and trace preorder, inorder, postorder, and level-order (BFS) tree traversals.
- Compare BFS and DFS as general traversal strategies for trees and graphs.
- Represent a graph using an adjacency list and an adjacency matrix, and pick the right one for a given problem.
- Explain the difference between directed, undirected, weighted, and acyclic graphs with real examples.
Quick Answer
A tree is a connected, hierarchical structure with no cycles — one root, and every other node has exactly one parent. A graph is more general: a set of vertices connected by edges, with no restriction on direction, cycles, or hierarchy (every tree is a graph, but not every graph is a tree). Trees model hierarchies like file systems and org charts; graphs model networks like roads, social connections, and web links. Both are traversed using the same two core strategies — depth-first (DFS) and breadth-first (BFS) — but how you represent them (linked nodes for trees, adjacency lists/matrices for graphs) and what traversal order means (preorder/inorder/postorder for trees) differs. This chapter builds the vocabulary and traversal mechanics; the next chapter on Graph Algorithms uses these building blocks for shortest paths and more.
Tree Terminology
Picture a family tree or a company's org chart — that's the intuition. A tree is a hierarchical data structure made of nodes connected by edges, with one special node at the top and no cycles.
| Term | Meaning |
|---|---|
| Root | The single top node — has no parent. Every tree has exactly one. |
| Node | A single element holding data (plus references to its children). |
| Edge | The connection between a parent and a child node. |
| Parent / Child | A node directly above/below another in the hierarchy. |
| Leaf | A node with no children — the "ends" of the tree. |
| Depth (of a node) | Number of edges from the root down to that node. The root has depth 0. |
| Height (of a tree) | The longest path from the root to any leaf (in edges). A single-node tree has height 0. |
| Subtree | Any node plus everything below it, treated as its own smaller tree. |
Why it matters: height directly drives performance. A balanced binary tree with n nodes has height O(log n), so search takes O(log n). An unbalanced tree (imagine inserting 1, 2, 3, 4, 5 in order into a BST) degenerates into a straight line — height O(n) — and search becomes as slow as a linked list.
Common misunderstanding: students often confuse depth and height. Depth is measured from the root down to a specific node; height is a property of the whole tree (or subtree), measured from a node down to its deepest leaf. The root's depth is always 0, but the tree's height depends on how deep the tree actually goes.
Binary Trees
A binary tree restricts each node to at most two children, conventionally called left and right.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Real-world example: expression trees. (3 + 4) * 5 becomes a tree where internal nodes are operators and leaves are operands — * at the root, with + as its left child (which itself has leaves 3 and 4) and 5 as its right child. Evaluating the tree bottom-up (postorder) computes the expression.
Binary Search Tree (BST)
A BST adds one rule: for every node, everything in the left subtree is smaller, everything in the right subtree is larger.
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def search(root, value):
if root is None or root.value == value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
That ordering rule is what makes search fast: at each node you eliminate an entire half of the remaining values, just like binary search on a sorted array.
Why it matters: BSTs back things like in-memory sorted sets, database index structures (B-trees are a generalized cousin), and language runtime maps that need ordered iteration.
Common misunderstanding: "a BST is always fast." Only a balanced BST guarantees O(log n). Insert already-sorted data into a plain BST and you get a degenerate linked list with O(n) operations — this is exactly why self-balancing trees like AVL and Red-Black trees exist (they rebalance automatically after every insert/delete).
| Operation | Balanced BST | Unbalanced (worst case) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Tree Traversals
Traversal means "visit every node exactly once." For trees, order matters and gives you different information.
def preorder(node, out):
if node:
out.append(node.value) # visit root first
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value) # visit root in the middle
inorder(node.right, out)
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value) # visit root last
from collections import deque
def level_order(root):
if not root:
return []
out, queue = [], deque([root])
while queue:
node = queue.popleft()
out.append(node.value)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return out
For the BST built from inserting 5, 3, 8, 1, 4:
- Inorder gives
1, 3, 4, 5, 8— sorted order, always, for any BST. This is the traversal to remember for exams. - Preorder gives
5, 3, 1, 4, 8— useful for copying/serializing a tree, since the root comes before its subtrees. - Postorder gives
1, 4, 3, 8, 5— useful for deleting a tree safely (children before parent) or evaluating expression trees. - Level-order (BFS) gives
5, 3, 8, 1, 4— visits by depth, useful when you care about "closest nodes first," like finding the shortest number of hops from the root.
Real-world example: your file explorer's "expand all folders" prints a preorder traversal (folder, then its contents); calculating total disk usage of a folder needs postorder (sum up children before reporting the parent's total).
Preorder/inorder/postorder are all depth-first — they use the call stack (or an explicit stack) to go deep before backtracking. Level-order is breadth-first — it uses a queue to expand outward one depth level at a time. That DFS-vs-BFS distinction is the one that carries over directly to graphs.
Graphs
A graph drops the hierarchy requirement entirely: it's just a set of vertices (nodes) and edges (connections) between them, with no rule about parents, children, or cycles.
| Term | Meaning |
|---|---|
| Vertex | A node in the graph. |
| Edge | A connection between two vertices. |
| Degree | Number of edges touching a vertex. |
| Path | A sequence of edges connecting two vertices. |
| Cycle | A path that returns to its starting vertex. |
Directed, Undirected, Weighted, Acyclic
- Undirected graph — edges go both ways. Example: Facebook friendships (if A is friends with B, B is friends with A).
- Directed graph (digraph) — edges have a direction. Example: Twitter/X "follows" (you can follow someone who doesn't follow you back), or task dependencies in a build system.
- Weighted graph — edges carry a cost/distance. Example: road networks, where edge weight = distance or travel time; this is what powers GPS routing.
- DAG (Directed Acyclic Graph) — directed, no cycles. Example: course prerequisite charts, or a spreadsheet's cell-dependency graph — you can't have Course A require Course B which requires Course A.
Representing a Graph in Code
Adjacency list — each vertex stores a list of its neighbors:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
Adjacency matrix — an n x n grid where matrix[i][j] = 1 (or the weight) if an edge exists:
# A B C D
matrix = [
[0, 1, 1, 0], # A
[1, 0, 0, 1], # B
[1, 0, 0, 1], # C
[0, 1, 1, 0], # D
]
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Check if edge (u, v) exists | O(degree of u) | O(1) |
| Iterate all neighbors of u | O(degree of u) | O(V) |
| Best for | Sparse graphs (roads, social graphs) | Dense graphs, or when you need instant edge lookups |
Common misunderstanding: students assume adjacency matrices are always "better" because lookup is O(1). For a sparse graph — say, a social network with a billion users but each person has only a few hundred friends — a matrix would need to store a billion x billion grid, almost entirely zeros. The adjacency list only pays for edges that actually exist, which is why it's the default choice for most real-world graphs.
Graph Traversal: BFS and DFS
The exact same two ideas from tree traversal apply here, just adapted since graphs can have cycles (so you must track visited nodes).
from collections import deque
def bfs(graph, start):
visited, order = {start}, []
queue = deque([start])
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited, order = set(), []
visited.add(start)
order.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
Why it matters: BFS explores outward layer by layer, so it's the natural fit for "shortest number of hops" problems (e.g., degrees of separation on LinkedIn). DFS dives deep before backtracking, so it's the natural fit for exhaustive exploration — detecting cycles, finding connected components, or solving mazes. The next chapter (Graph Algorithms) builds Dijkstra's and other shortest-path algorithms directly on top of these two primitives.
Visual: Tree vs. Graph Traversal
Notice D has two parents (reachable from both B and C) — that single detail is what makes this a graph, not a tree. In a tree, every node (except the root) has exactly one parent; here, D has two, and if you trace A → B → D → C → A you'd also have a cycle if an edge from C back to A existed. A BFS from A visits in order A, B, C, D, E (queue-based, layer by layer); a DFS from A visits A, B, D, C, E (stack-based, diving deep down the B branch before backing out to C).
Key Terms
| Term | Definition |
|---|---|
| Root | The top node of a tree; has no parent. |
| Leaf | A node with no children. |
| Height | Longest root-to-leaf path in a tree (in edges). |
| Depth | Number of edges from the root to a given node. |
| Binary Search Tree (BST) | A binary tree where left subtree < node < right subtree, enabling O(log n) search when balanced. |
| Traversal | Visiting every node exactly once, in a defined order (preorder, inorder, postorder, level-order). |
| Vertex | A node in a graph. |
| Edge | A connection between two vertices, optionally directed and/or weighted. |
| Adjacency List | Graph representation storing each vertex's neighbors in a list; efficient for sparse graphs. |
| Adjacency Matrix | Graph representation using an n x n grid; efficient for dense graphs or O(1) edge checks. |
| DAG | Directed Acyclic Graph — directed edges, no cycles; used for dependency/scheduling problems. |
| BFS | Breadth-First Search — explores level by level using a queue. |
| DFS | Depth-First Search — explores as deep as possible before backtracking, using a stack/recursion. |
Common Mistakes
-
Misconception: "A tree is just a graph with a fancy name." Why it's wrong: All trees are graphs, but not all graphs are trees. A tree specifically has no cycles and exactly one path between any two nodes, with a single root and every non-root node having exactly one parent. Correct understanding: Think of "tree" as a graph with two extra constraints: connected and acyclic. A graph can have cycles, multiple parents per node, disconnected pieces, or no designated root at all.
-
Misconception: "BST operations are always O(log n)." Why it's wrong: O(log n) only holds if the tree stays reasonably balanced. Inserting sorted or nearly-sorted data into a plain BST produces a degenerate, linked-list-shaped tree. Correct understanding: Plain BSTs are O(log n) average case but O(n) worst case. Guaranteed O(log n) requires a self-balancing tree (AVL, Red-Black) that rebalances after inserts/deletes.
-
Misconception: "DFS and BFS always find the shortest path." Why it's wrong: BFS finds the shortest path only in unweighted graphs, because it explores layer by layer. DFS doesn't guarantee shortest path at all — it just happens to find a path. Correct understanding: For weighted graphs, you need algorithms like Dijkstra's (covered in the Graph Algorithms chapter) that account for edge weights, not just hop count.
Comparison and Connections
| Concept A | Concept B | Key Difference |
|---|---|---|
| Tree | Graph | Tree = connected, acyclic, one root, one parent per node. Graph = no such restrictions; can have cycles and multiple parents. |
| BFS | DFS | BFS uses a queue, explores level by level, finds shortest path in unweighted graphs. DFS uses a stack/recursion, dives deep first, better for exhaustive search and cycle detection. |
| Adjacency List | Adjacency Matrix | List is space-efficient for sparse graphs (O(V+E)); matrix gives O(1) edge lookup but costs O(V²) space. |
| Preorder/Postorder | Inorder | Inorder is specific to binary trees and yields sorted order for a BST; pre/postorder are general-purpose (serialization, cleanup) and don't imply sorted output. |
| Directed Graph | Undirected Graph | Directed edges represent one-way relationships (follows, dependencies); undirected edges represent mutual relationships (friendships, roads without one-way restrictions). |
Practice Questions
Recall
-
What is the difference between the depth of a node and the height of a tree? Answer guidance: Depth is measured from the root down to a specific node (root = depth 0). Height is the longest path from a node (often the root) down to its deepest leaf.
-
Name the four standard tree traversal orders. Answer guidance: Preorder (root, left, right), inorder (left, root, right), postorder (left, right, root), and level-order/BFS (by depth, using a queue).
Understanding
-
Why does inorder traversal of a BST always produce values in sorted order? Answer guidance: Because at every node, the BST property guarantees everything in the left subtree is smaller and everything in the right subtree is larger. Visiting left, then the node, then right at every recursive step therefore always processes values in ascending order.
-
Why is an adjacency list usually preferred over an adjacency matrix for real-world graphs like social networks? Answer guidance: Real-world graphs are typically sparse (each vertex connects to relatively few others). An adjacency list costs O(V+E) space, scaling with actual edges; a matrix costs O(V²) regardless of how many edges exist, wasting huge amounts of memory on non-existent connections.
Application
-
You need to print a company's org chart so that each manager is listed before their direct reports. Which traversal do you use, and why? Answer guidance: Preorder — it visits (prints) the current node before recursing into its children, matching "manager before reports."
-
You're building a "shortest number of connections between two people" feature (like LinkedIn's "2nd-degree connection"). Would you use BFS or DFS, and why? Answer guidance: BFS, because it explores the graph layer by layer from the start, so the first time it reaches the target node is guaranteed to be via the shortest (fewest-hops) path in an unweighted graph.
Analysis
-
A BST is built by inserting the values
1, 2, 3, 4, 5in that order. What does the tree look like, and what does this reveal about BST performance guarantees? Answer guidance: Each new value is larger than the last, so every node only has a right child — the tree degenerates into a straight line (like a linked list) with height 4 (O(n)). This shows plain BSTs don't guarantee O(log n); only self-balancing variants (AVL, Red-Black trees) do. -
Compare representing a road network as (a) an adjacency matrix vs (b) an adjacency list, given that most cities only connect directly to a handful of neighboring cities. Which is more appropriate and why? Answer guidance: Adjacency list. With thousands of cities but each connecting to only a few neighbors, the graph is sparse — a matrix would allocate space for every possible city pair (mostly unused), while a list only stores real connections, saving massive amounts of memory with no loss of correctness.
FAQ
Q: Is a linked list a type of tree? A: Sort of — a singly linked list is structurally a degenerate tree where every node has at most one child. It's a useful mental model for understanding why unbalanced BSTs perform badly: in the worst case, they collapse into exactly this shape.
Q: Can a tree have more than one root? A: No — by definition a tree has exactly one root. If you have multiple disconnected trees together, that collection is called a forest.
Q: What's the difference between a tree and a heap? A: A heap is a specific kind of binary tree with an ordering rule about parent/child values (parent always smaller in a min-heap, or always larger in a max-heap), used to efficiently get the minimum/maximum element. It's not sorted like a BST — only the parent-child relationship is guaranteed, not left-vs-right.
Q: Do I need to memorize BFS/DFS code for exams? A: You should be able to write both from scratch: BFS with a queue and a visited set, DFS with recursion (or an explicit stack) and a visited set. The visited-set part is the detail students most often forget, and without it a cyclic graph traversal never terminates.
Q: Why do we care about DAGs specifically? A: Because "directed + acyclic" is exactly the condition needed for topological sorting — arranging tasks so every dependency comes before the tasks that need it. This shows up in build systems, course scheduling, and spreadsheet formula evaluation.
Q: Is DFS always implemented with recursion? A: No — recursion is just a convenient way to use the call stack implicitly. You can implement DFS iteratively with an explicit stack data structure, which is often necessary for very deep graphs to avoid a stack overflow.
Quick Revision
- Tree = connected, acyclic graph with one root; every non-root node has exactly one parent.
- Depth = distance from root to a node; height = longest root-to-leaf path.
- Binary tree: at most 2 children per node. BST adds: left < node < right, everywhere.
- BST search/insert/delete: O(log n) average (balanced), O(n) worst case (unbalanced/degenerate).
- Inorder traversal of a BST always yields sorted order — remember this for exams.
- Preorder = root first (serialization); Postorder = root last (safe deletion, expression evaluation).
- Level-order traversal = BFS on a tree, using a queue.
- Graph = vertices + edges, no hierarchy requirement, cycles allowed.
- Adjacency list: O(V+E) space, best for sparse graphs. Adjacency matrix: O(V²) space, O(1) edge lookup, best for dense graphs.
- BFS = queue, layer by layer, shortest path in unweighted graphs. DFS = stack/recursion, dives deep, good for cycle detection and exhaustive search.
- DAG = Directed Acyclic Graph — the foundation for topological sorting and dependency scheduling.
Related Topics
Prerequisites
- 1. Introduction to Data Structures
- 2. Arrays and Strings
- 4. Stacks and Queues (needed for iterative DFS/BFS implementations)
Related Topics
- 6. Hashing and Hash Tables (used alongside "visited" sets in graph traversal)
- Recursion and the call stack (underlies DFS and tree traversals)
Next Topics
- 10. Graph Algorithms — Dijkstra's, Bellman-Ford, and shortest-path/topological-sort algorithms built on the BFS/DFS foundations covered here.