Data Structures II (Hierarchical & Networked)

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

Your computer's file system is a tree: the root directory (C:\ or /) at the top, folders as internal nodes, files as leaves. Every file has exactly one parent folder. There are no loops. To find a file, you navigate root → folder → subfolder → file — one unique path.

Analogy:

Your computer's file system is a tree: the root directory (C:\ or /) at the top, folders as internal nodes, files as leaves. Every file has exactly one parent folder. There are no loops. To find a file, you navigate root → folder → subfolder → file — one unique path.

Definition:

A tree is a connected, acyclic graph with one root node. Terminology: root (top node), leaf (childless node), depth (distance from root), height (max depth), subtree (any node + its descendants). Number of edges = n − 1. Between any two nodes there is exactly one path. Trees are inherently recursive: each subtree is itself a tree.

Real file systems have symbolic links creating multiple paths to the same file, violating the tree property and turning the structure into a graph. The family-tree analogy also breaks because real people have two biological parents, while tree nodes have exactly one parent.

<html>          (depth 0, root)
  <head>        (depth 1)
  <body>        (depth 1)
    <div>       (depth 2)
      <p>       (depth 3, leaf)

Height = 3, Edges = Nodes − 1 = 4

The browser walks this tree from <html> downward — this is the basis for document.querySelector. Every node has exactly one parent, and there are no cycles.

Tree

No cycles, one root, exactly one path between any two nodes. Edges = n − 1. Strict hierarchy.

Graph

Cycles allowed, no root required, multiple paths possible. Flexible connections without fixed hierarchy.

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

Searching a phone book: you open it near the middle, check if your name is before or after, then repeat in the relevant half. A BST makes this halving a permanent structure — each node is a decision point directing you left (smaller) or right (larger).

Analogy:

Searching a phone book: you open it near the middle, check if your name is before or after, then repeat in the relevant half. A BST makes this halving a permanent structure — each node is a decision point directing you left (smaller) or right (larger).

Definition:

A BST is a binary tree (max 2 children per node) with an ordering invariant: all keys in the left subtree < node key < all keys in the right subtree. Search halves the search space at each step — O(log n) when balanced (height ≈ log₂ n). If elements are inserted in sorted order, the BST degenerates into a linked list with height n and O(n) operations.

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.

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,000 (linear)

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.

Balanced vs. Degenerate

Balanced BST — O(log n) Insert [50, 30, 70, 20, 40, 60, 80]: height ≈ 3 (log₂ 7). Search: max 3 comparisons for 7 elements.

Degenerate BST — O(n) Insert [10, 20, 30, 40, 50]: right-leaning chain, height = 4. Search for 50: 4 comparisons — no better than a linked list.

Same data structure, completely different behaviour — depending only on insertion order. This is exactly why self-balancing trees were invented.

Only when the tree is approximately balanced. Sorted insertion produces a chain with height n — 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 after every insert or delete to keep the height at ~log₂ n. The developer pays a small overhead per operation — but gains the guarantee that search never degenerates to O(n). Most standard libraries (e.g. std::map in C++, TreeMap in Java) use Red-Black trees internally.

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.

Search: 40

Step 1 / 3Compare root

The search starts at the root (50). The target value 40 is less than 50 — so the algorithm goes left.

40 < 50 → left

Graphs — The General Network

Imagine a subway map. Stations are nodes, rail connections are edges. Some lines are one-way (directed); travel times are edge weights. Between two stations there are often multiple routes with different total travel times — choosing the fastest is a shortest-path problem. Unlike a tree, a subway network has loops and no single root station.

Analogy:

Imagine a subway map. Stations are nodes, rail connections are edges. Some lines are one-way (directed); travel times are edge weights. Between two stations there are often multiple routes with different total travel times — choosing the fastest is a shortest-path problem. Unlike a tree, a subway network has loops and no single root station.

Definition:

A graph consists of vertices (nodes) and edges connecting pairs of vertices. Unlike trees, graphs allow cycles, multiple paths between nodes, and no designated root. Types: undirected (edges are symmetric) vs. directed (edges have direction); unweighted vs. weighted (edges carry costs like distance or time). Historical origin: Euler's Königsberg bridge problem (1736) — the first formal graph analysis.

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.

Undirected Edges go both ways. Example: Facebook friendship — if A is friends with B, B is friends with A.

Directed Edges have direction. Example: Twitter follow — A follows B does not mean B follows A.

Weighted Edges carry costs (distance, time). Example: road network with kilometre values.

Unweighted All edges are equal. Example: "knows" in a social network — no intensity measure.

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. Neural networks: layers as a directed acyclic graph (DAG).

A directed edge A→B does NOT imply B→A. On 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 next module, where we will write algorithms like breadth-first search (BFS) to 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 ]

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.

What distinguishes a tree from a general graph?

Trees can have cycles

A tree is a connected, acyclic graph with one root — every tree is a graph, but not every graph is a tree

Trees always have weighted edges

Trees always have exactly two children per node

1. What distinguishes a tree from a general graph?

☐ A) Trees can have cycles
☐ B) A tree is a connected, acyclic graph with one root — every tree is a graph, but not every graph is a tree
☐ C) Trees always have weighted edges
☐ D) Trees always have exactly two children per node

2. A balanced BST has 1,000,000 elements. Approximately how many comparisons does a search need?

☐ A) 500,000
☐ B) ~20
☐ C) 1,000,000
☐ D) 100

3. A social network has friendships (mutual) and follows (one-way). Which graph types do you need?

☐ A) Both undirected
☐ B) Both directed
☐ C) Friendships: undirected. Follows: directed
☐ D) Friendships: weighted. Follows: unweighted

4. You insert elements [10, 20, 30, 40, 50] into a BST in that order. Why is search slow in the result?

☐ A) BSTs cannot store more than 4 elements
☐ B) The sorted insertion order creates a right-leaning chain (height = n), making search O(n) instead of O(log n)
☐ C) BSTs cannot store integers
☐ D) The tree has no root

Answer Key: 1) B · 2) B · 3) C · 4) B

Checkpoint: Do You Understand Hierarchical Data Structures?

I can define a tree by its rules (root, parent, children, leaves, no cycles) and explain why every tree is a graph but not every graph is a tree.
I can trace a search in a BST and explain when it is O(log n) versus when it degenerates to O(n).
I can distinguish directed from undirected and weighted from unweighted graphs, and name one real-world system for each.

Data Structures II (Hierarchical & Networked)

Trees — Hierarchy with Rules

Tree

Analogy:

Definition:

Example: The DOM Tree

Misconception: Trees and Graphs Are Completely Different

Binary Search Trees — Ordered for Speed

Binary Search Tree (BST)

Analogy:

Definition:

BST Search: Step by Step

Balance Is Everything

Balanced vs. Degenerate

Misconception: BST Search Is Always O(log n)

Deep Dive: Self-Balancing Trees

Interactive: BST Search Step by Step

Graphs — The General Network

Graph

Analogy:

Definition:

Graphs in the Real World

Misconception: Directed Graphs Allow Travel in Both Directions

Deep Dive: How Are Graphs Stored?

Key Takeaways

Quiz: Hierarchical Data Structures

What distinguishes a tree from a general graph?

Checkpoint: Do You Understand Hierarchical Data Structures?

Trees — Hierarchy with Rules

Tree

Analogy:

Definition:

Example: The DOM Tree

Misconception: Trees and Graphs Are Completely Different

Binary Search Trees — Ordered for Speed

Binary Search Tree (BST)

Analogy:

Definition:

BST Search: Step by Step

Balance Is Everything

Balanced vs. Degenerate

Misconception: BST Search Is Always O(log n)

Deep Dive: Self-Balancing Trees

Interactive: BST Search Step by Step

Graphs — The General Network

Graph

Analogy:

Definition:

Graphs in the Real World

Misconception: Directed Graphs Allow Travel in Both Directions

Deep Dive: How Are Graphs Stored?

Key Takeaways

Quiz: Hierarchical Data Structures

What distinguishes a tree from a general graph?

Checkpoint: Do You Understand Hierarchical Data Structures?

Related Content

Article

Linear Data Structures

Data Structures III (Key-Based)

What Is an Algorithm?

Algorithmic Complexity

Graph Search — The Beginnings

Heuristics & Pathfinding: From Dijkstra to A*

MinMax & Pruning

Recursion

Demo

MinMax (Game Theory)

Pathfinding (Graph Search)

Glossary

Timeline