Back to Learning Area

Data Structures II (Hierarchical & Networked)

Trees, search trees, and graphs — data structures with family relationships.

  • Fundamentals
  • 15 min
  • Intermediate

Plain Language

This preview is in Plain Language. The whole portal is also available in Plain Language. You can change the language at the top. Or use the button below. Our Plain Language texts are AI-assisted and editorially reviewed. They follow the core principles of easy-to-read language, but they are not certified Easy Read: a review panel of people with learning difficulties does not test them.

Preview: Understanding trees and graphs

What is a tree?

A tree is like a folder system. The root is at the top. Leaves are at the bottom. Between them, there are branches. Every point has exactly one parent point.

Binary search trees

A search tree is a tree with an order. Binary means: every point has a left and a right. Smaller numbers are on the left. Larger numbers are on the right. This is how you find numbers very fast.

Graphs everywhere

A graph is a network. It has points and connections. A road network is a graph. The internet is a graph. Social networks are also graphs.

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

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.

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 = 4

The 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.

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.

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

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).

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. 1. Search 40: compare with root 50 → 40 < 50, go left
  2. 2. Compare with 30 → 40 > 30, go right
  3. 3. Compare with 40 → found! Only 3 comparisons
  4. 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

Balanced BST — O(log n) Insert [50, 30, 70, 20, 40, 60, 80]: height = 2, i.e. 3 levels (log₂(7 + 1) = 3). 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: 5 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.

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.

50 30 70 20 40 60 80
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
Controls
Steps

Graphs — The General Network

Definition

Graph

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.

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: following on X (formerly Twitter) — 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.

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

  1. 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.
  2. 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.
  3. 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

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

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