Data Structures II (Hierarchical & Networked)
Trees, search trees, and graphs — data structures with family relationships.
After arrays and linked lists, you might think data always sits in a line. But most real-world relationships are hierarchical (folders, org charts) or networked (roads, social connections). Trees and graphs capture these shapes — and the algorithms that traverse them power everything from web browsers to navigation apps.
This article introduces the three structures that bridge linear data and the search algorithms you will study next: trees, binary search trees, and graphs.
Trees — Hierarchy with Rules
Definition
Tree
Analogy
Definition
Real file systems have symbolic links creating multiple paths to the same file, violating the tree property and turning the structure into a graph. A family tree is, strictly speaking, not a tree either, because real people have two biological parents, while tree nodes have exactly one parent.
Example: The DOM Tree
<html> (depth 0, root)
<head> (depth 1, leaf)
<body> (depth 1)
<div> (depth 2)
<p> (depth 3, leaf)
Height = 3, Edges = Nodes − 1 = 4The browser walks this tree from <html> downward — this is the basis for document.querySelector. Every node except the root has exactly one parent, and there are no cycles.
No cycles, one root, exactly one path between any two nodes. Edges = n − 1. Strict hierarchy.
Cycles allowed, no root required, multiple paths possible. Flexible connections without fixed hierarchy.
Caution
Misconception: Trees and Graphs Are Completely Different
Every tree IS a graph — specifically a connected, acyclic graph. The relationship is subset, not separate category. Understanding this prevents treating trees and graphs as unrelated topics.
Binary Search Trees — Ordered for Speed
Definition
Binary Search Tree (BST)
Analogy
Definition
A phone book is flat and sequential; a BST is hierarchical. Also, the logarithmic guarantee depends on balance — sorted insertion creates a "one-page phone book" (linked list). The analogy hides the balance requirement.
Note
BST Search: Step by Step
- 1. Search 40: compare with root 50 → 40 < 50, go left
- 2. Compare with 30 → 40 > 30, go right
- 3. Compare with 40 → found! Only 3 comparisons
- 4. With 1,000,000 elements: ~20 comparisons instead of ~500,000linear
At each step, half the remaining data is discarded. That is why search is logarithmic — the same principle as binary search on a sorted array, but with dynamic insert and delete.
Note
Balance Is Everything
Balanced vs. Degenerate
Same data structure, completely different behaviour — depending only on insertion order. This is exactly why self-balancing trees were invented.
Caution
Misconception: BST Search Is Always O(log n)
Only when the tree is approximately balanced. Sorted insertion produces a chain with height n − 1 — no better than linear search. This is precisely why self-balancing variants like AVL and Red-Black trees exist.
AVL trees and Red-Black trees rotate nodes as needed after an insert or delete to keep the height on the order of log₂ n (AVL at most about 1.44 · log₂ n, Red-Black at most about 2 · log₂ n). The developer pays a small overhead per operation — but gains the guarantee that search never degenerates to O(n). Many standard libraries use Red-Black trees internally, such as TreeMap in Java and, usually, std::map in C++.
Interactive: BST Search Step by Step
You learned that a BST halves the search space with each comparison. Click through the steps of a real search and observe how the algorithm traverses the tree — node by node, comparison by comparison.
The search starts at the root (50). The target value 40 is less than 50 — so the algorithm goes left.
Graphs — The General Network
Definition
Graph
Analogy
Definition
Subway networks are bound by geography, Euclidean distances, and physical laws. Abstract graphs have no such constraints — a node in Tokyo can have a direct edge with cost 0 to a node in Berlin.
Note
Graphs in the Real World
Road networks: cities as nodes, roads as weighted edges — Dijkstra's algorithm (1959) finds the shortest path. The Web: pages as nodes, links as directed edges — Google's PageRank ranks pages by incoming links. Social networks: users as nodes, relationships as edges. Feedforward neural networks: neurons as nodes, weighted connections as directed edges — a directed acyclic graph (DAG).
Caution
Misconception: Directed Graphs Allow Travel in Both Directions
A directed edge A→B does NOT imply B→A. On X (formerly Twitter), if you follow someone, they do not automatically follow you back. Each direction requires its own explicit edge.
Two common representations: adjacency list (list of neighbours per node — memory-efficient for sparse graphs) and adjacency matrix (n×n table — fast edge lookups, but memory-hungry for large sparse graphs). This Python dictionary representation (adjacency list) is the foundation for the article “Graph Search”, where algorithms like breadth-first search (BFS) find the shortest path through a network.
# Adjacency list (Python dict)
graph = {
"A": ["B", "C"],
"B": ["C"],
"C": ["A"]
}
# Adjacency matrix
# A B C
# A [ 0, 1, 1 ]
# B [ 0, 0, 1 ]
# C [ 1, 0, 0 ]Note
Key Takeaways
- A tree is a connected, acyclic graph with one root. Its strictness (no cycles, one parent per node) is what makes recursive algorithms and efficient search possible.
- A BST adds an ordering rule to a binary tree, achieving O(log n) search when balanced — but degenerates to O(n) when unbalanced. Balance is the critical quality factor.
- Graphs are the most general relationship structure: directed or undirected, weighted or unweighted, with or without cycles — and every tree is just a very disciplined graph.
Check
Quiz: Hierarchical Data Structures
What distinguishes a tree from a general graph?
Select one answer
1. What distinguishes a tree from a general graph?
2. A balanced BST has 1,000,000 elements. Approximately how many comparisons does a search need?
3. A social network has friendships (mutual) and follows (one-way). Which graph types do you need?
4. You insert elements [10, 20, 30, 40, 50] into a BST in that order. Why is search slow in the result?
Check
Checkpoint: Do You Understand Hierarchical Data Structures?
Can you explain this in your own words? Tick what you've got.
0 of 3 done