Data Structures & Algorithms

An algorithm is a precise, finite sequence of steps that solves a problem. A data structure is a way of organizing data in memory so those steps can run efficiently. This course is about pairing the two: the same problem can be solved by many algorithms over many structures, and the choice can mean the difference between an answer in a second and an answer in a week.

Why not just time it?

Timing a program with a stopwatch is tempting but unreliable. The number of seconds depends on your CPU, the programming language, what else the machine is doing, and the exact input you happened to pick. Instead we count the number of basic operations (comparisons, assignments, arithmetic) an algorithm performs as a function of the input size, usually called n. This gives a machine-independent measure that predicts how the cost grows as the input grows, which is what actually matters at scale.

Best, worst, and average case

The same algorithm can do different amounts of work on different inputs of the same size. Consider searching a list of n items one by one for a target:

• Best case: the target is the first item. One comparison.
• Worst case: the target is last or absent. About n comparisons.
• Average case: over random positions, about n/2 comparisons.

We care most about the worst case, because it is a guarantee: the algorithm will never be slower than that. Occasionally we also study the average case when the worst case is rare and pessimistic.

A first look at growth

Here is a loop that sums the numbers from 0 to n minus 1. It does a fixed amount of setup, then a chunk of work once per item.

def total(n):
    s = 0                 # 1 operation
    for i in range(n):    # runs n times
        s = s + i         # 1 operation each time
    return s              # 1 operation

The work is roughly n + 2 operations. As n gets large, the "+2" stops mattering; what dominates is that the cost is proportional to n. Capturing exactly that idea, and ignoring the details that do not matter at scale, is the job of Big-O notation, which we meet next.

Big-O notation describes an upper bound on how the running time (or memory) of an algorithm grows as the input size n grows. When we say an algorithm is O(n), we mean that beyond some input size its cost grows no faster than a constant times n. Big-O deliberately throws away detail so we can compare algorithms by their shape of growth, not their exact instruction counts.

Two simplification rules

To move from an operation count to a Big-O class, apply two rules:

1. Drop constant factors. 5n and 100n are both O(n). Constants depend on the machine and are not the point.
2. Drop lower-order terms. In n^2 + n + 7, the n^2 term dominates for large n, so the whole thing is O(n^2).

The common growth classes

From fastest-growing (bad) to slowest-growing (good), the classes you will meet all course are:

Big-O	Name	Example
O(1)	Constant	Array index lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Scanning a list once
O(n log n)	Linearithmic	Merge sort, quicksort (average)
O(n^2)	Quadratic	Bubble, insertion, selection sort
O(2^n)	Exponential	Naive subset enumeration

Not just an upper bound

Two related symbols make the picture precise. Big-Omega (written with the Greek letter Omega) is a lower bound: the cost grows at least this fast. Big-Theta (Theta) is a tight bound: the cost grows exactly this fast, both above and below. If an algorithm is both O(n) and Omega(n), then it is Theta(n). In casual use people say "O" when they really mean a tight bound, but knowing the difference keeps your reasoning honest.

Worked example

Consider a nested loop:

def count_pairs(items):
    c = 0
    for i in items:        # n times
        for j in items:    # n times, for each i
            c = c + 1      # runs n * n times total
    return c

The inner line runs n times for each of the n outer passes, so n * n = n^2 times. This algorithm is O(n^2). If we added a separate single loop before it, the total would be n^2 + n, which simplifies back to O(n^2) by dropping the lower term.

Running time is only half the story. Space complexity measures how much memory an algorithm needs as a function of the input size n, again expressed in Big-O. We usually care about auxiliary space: the extra memory beyond the input itself.

Counting extra memory

Compare two ways to double every number in a list. The first modifies the list in place; the second builds a brand new list.

def double_in_place(a):
    for i in range(len(a)):
        a[i] = a[i] * 2      # no new list; O(1) extra space

def double_copy(a):
    result = []
    for x in a:
        result.append(x * 2) # new list of size n; O(n) extra space
    return result

Both do O(n) work in time. But double_in_place uses only a fixed number of extra variables, so its auxiliary space is O(1), while double_copy allocates a new list of n items, so its auxiliary space is O(n).

Recursion costs space too

Every pending function call occupies a frame on the call stack. A recursion that goes n levels deep before returning uses O(n) space on the stack even if it creates no data structures. We will see this clearly with recursive sorts, where the recursion depth drives the space bound.

The time-space trade-off

Often you can spend memory to save time, or vice versa. A classic example is memoizing (caching) results: storing answers you have already computed uses extra space but avoids recomputing them, turning some slow recursions into fast ones. Choosing the right point on that trade-off is a core engineering judgment, and stating both the time and space complexity of your solution is how you make the trade-off visible.

An array is a block of memory holding elements of the same type in consecutive slots. Because the slots are contiguous and equally sized, the computer can jump straight to any element by arithmetic: the address of element i is the start address plus i times the element size. That single calculation is why indexing is O(1), no matter how large the array is.

The catch: fixed size

A classic (static) array has a fixed length chosen when it is created. To store one more element than it holds, you must allocate a bigger block and copy everything over. Inserting or deleting in the middle is also costly: every later element must shift by one slot, which is O(n).

Dynamic arrays

A dynamic array hides the fixed-size problem. Python's list is one. It keeps a larger backing block than it currently needs (spare capacity). Appending is O(1) while there is spare room. When the block fills, the dynamic array allocates a new block, typically double the size, and copies the old elements over, which costs O(n) for that one append.

Doubling is the key trick. Because the array doubles, those expensive copy-everything appends happen rarely and get geometrically farther apart. Averaged over a long run of appends, the cost per append is a constant. We call this amortized O(1): any single append might be O(n), but the average over many appends is O(1).

a = []                 # empty dynamic array (Python list)
for i in range(1000):
    a.append(i)        # each append is amortized O(1)
print(a[500])          # O(1) index lookup

Complexity summary

Operation	Complexity
Index (read/write a[i])	O(1)
Append to end	O(1) amortized
Insert or delete at front/middle	O(n)
Search for a value	O(n)

Space for a dynamic array is O(n): it stores n elements plus a bounded amount of spare capacity. Arrays are the workhorse structure; reach for them whenever you need fast indexed access and mostly append at the end.

A linked list stores elements in separate nodes scattered through memory. Each node holds a value and a pointer (a reference) to the next node. A variable called head points to the first node; the last node points to nothing (in Python, None). Because nodes are linked by pointers rather than laid out contiguously, the list can grow and shrink without ever copying or shifting a block of memory.

Building one in Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Build the list 10 -> 20 -> 30
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

# Traverse it
node = head
while node is not None:
    print(node.value)
    node = node.next

The fundamental trade-off with arrays

Linked lists and arrays are mirror images. To reach the i-th element of a linked list you must follow pointers from the head, one node at a time, so access is O(n), whereas an array gives O(1) indexing. But once you already hold a node, inserting or deleting next to it is just a couple of pointer reassignments, which is O(1), whereas an array must shift elements in O(n).

Operation	Array	Linked list
Access i-th element	O(1)	O(n)
Insert/delete at front	O(n)	O(1)
Insert/delete after a known node	O(n)	O(1)
Search for a value	O(n)	O(n)

Variations and cost

A singly linked list points only forward. A doubly linked list adds a prev pointer in each node so you can walk backward and delete a node in O(1) given only that node. The price is extra memory: linked lists use O(n) space like arrays, but each node also stores one or two pointers, so the constant factor is higher. Choose a linked list when you insert and delete at the ends constantly and rarely need random indexed access.

Stacks and queues are restricted linear structures: they limit where you may add and remove items, and that restriction is exactly what makes them useful.

Stack: last in, first out

A stack follows LIFO order, last in, first out, like a stack of plates. You push onto the top and pop off the top; you never touch the middle. A Python list makes a perfect stack because appending and popping at the end are both O(1).

stack = []
stack.append("a")   # push
stack.append("b")   # push
top = stack.pop()   # pop -> "b" (LIFO)
print(top, stack)   # b ['a']

Stacks appear everywhere: the function call stack, undo buttons, matching brackets, and depth-first search later in this course. Both push and pop are O(1).

Queue: first in, first out

A queue follows FIFO order, first in, first out, like a line at a store. You enqueue at the back and dequeue from the front. A Python list is a poor queue: popping from the front is O(n) because everything shifts. Instead use collections.deque, a double-ended queue that adds and removes at both ends in O(1).

from collections import deque
q = deque()
q.append("a")        # enqueue at back
q.append("b")
first = q.popleft()  # dequeue from front -> "a" (FIFO)
print(first, q)      # a deque(['b'])

Queues model anything served in arrival order: print jobs, task scheduling, and breadth-first search later on. With a deque, enqueue and dequeue are both O(1).

Summary

Structure	Order	Add	Remove
Stack	LIFO	push O(1)	pop O(1)
Queue (deque)	FIFO	enqueue O(1)	dequeue O(1)

Both use O(n) space to hold n items. The lesson: pick the discipline that matches your problem, LIFO for "most recent first," FIFO for "oldest first."

A hash table stores key-value pairs and finds a key in O(1) average time, far faster than scanning a list. It is the structure behind Python's dict and set. The magic is a hash function: it takes a key and computes an integer, which is reduced (with the modulo operator) to an index into an underlying array of buckets. To store or find a key you hash it, jump straight to that bucket, and look there. No scanning required.

prices = {}                 # a dict is a hash table
prices["apple"] = 30        # hash "apple" -> a bucket, store there
prices["banana"] = 10
print(prices["apple"])      # hash again -> same bucket -> 30, O(1) average
print("banana" in prices)   # membership test, O(1) average

Collisions

Different keys can hash to the same bucket. This is a collision, and it is unavoidable because there are more possible keys than buckets. A common fix is separate chaining: each bucket holds a small linked list of all pairs that landed there. To find a key you hash to its bucket, then walk that short list. If the hash function spreads keys evenly and the table is not too full, each list stays tiny, so lookups stay effectively O(1) on average.

Load factor and resizing

The load factor is the number of stored items divided by the number of buckets. As it rises, chains get longer and lookups slow down. So hash tables resize: when the load factor crosses a threshold (often around 0.7), they allocate a larger bucket array and rehash every key into it. Like dynamic-array doubling, this makes insertion amortized O(1).

Honest complexity

Operation	Average	Worst case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

The worst case is O(n), which happens if a bad hash function dumps every key into one bucket, degrading the table to a single long list. In practice, good hash functions make that vanishingly rare, so hash tables are the default choice for fast lookup, deduplication, and counting. Space is O(n).

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every correct recursion has two parts: a base case that returns an answer directly without recursing, and a recursive case that reduces the problem and calls itself. Omit the base case and the function calls forever, eventually crashing with a stack overflow.

Factorial: the classic

def factorial(n):
    if n == 0:                 # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(5))            # 120

To evaluate factorial(5), Python suspends it to compute factorial(4), and so on down to factorial(0), which returns 1. Then the answers multiply back up: 1, 1, 2, 6, 24, 120. There are n plus 1 calls, each doing O(1) work, so factorial is O(n) time. The n stacked calls make it O(n) space.

Recursion and the call stack

Each active call keeps a frame on the call stack until it returns. The maximum number of frames alive at once is the recursion depth, and it sets the space complexity. This is why deeply recursive code can exhaust memory even when it makes no data structures.

When recursion shines

Recursion is the natural fit for self-similar problems, ones whose solution is built from solutions to smaller copies of themselves: walking a folder tree, exploring a maze, or the divide-and-conquer sorts in the next module. A useful idea is divide and conquer: split the problem into smaller independent parts, solve each recursively, and combine the results. Anything recursive can be rewritten with a loop and an explicit stack, but for self-similar problems the recursive version is usually far clearer. Always write the base case first, and make sure every recursive call moves toward it.

def count_down(n):
    if n == 0:            # base case
        print("done")
        return
    print(n)
    count_down(n - 1)     # moves toward the base case

count_down(3)            # 3, 2, 1, done

Sorting arranges items into order, and it is one of the most studied problems in computing. We start with two simple comparison sorts that are easy to understand, then build to faster ones. Both sorts here run in O(n^2) time in the worst case, which makes them slow on large inputs but instructive and useful on small ones.

Bubble sort

Bubble sort repeatedly walks the list, comparing each adjacent pair and swapping them if they are out of order. Each full pass "bubbles" the largest remaining element to the end. After at most n minus 1 passes the list is sorted.

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]  # swap
    return a

Two nested loops over n elements give O(n^2) comparisons in the worst and average case. It sorts in place, so space is O(1). Bubble sort is rarely used in practice; its value is pedagogical.

Insertion sort

Insertion sort builds the sorted list one item at a time. It takes each element and inserts it into its correct spot among the already-sorted elements to its left, shifting larger ones right, exactly how many people sort a hand of playing cards.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift right
            j = j - 1
        a[j + 1] = key        # drop key into place
    return a

Why insertion sort is worth knowing

Insertion sort is O(n^2) worst case (a reverse-sorted list), but O(n) in the best case when the list is already nearly sorted, because the inner while loop barely runs. It is in place (O(1) space) and stable (it keeps equal elements in their original order). For small or nearly sorted arrays it beats fancier sorts, which is why real sorting libraries switch to insertion sort on small chunks.

Sort	Best	Average	Worst	Space
Bubble	O(n)	O(n^2)	O(n^2)	O(1)
Insertion	O(n)	O(n^2)	O(n^2)	O(1)

Note: bubble sort reaches its O(n) best case only with an optimization that stops early when a pass makes no swaps.

The quadratic sorts are simple but slow. The two great divide-and-conquer sorts, merge sort and quicksort, reach O(n log n), which is the best possible for comparison-based sorting. The log n factor comes from repeatedly halving the problem; the n factor comes from doing linear work at each level.

Merge sort

Merge sort splits the list in half, recursively sorts each half, then merges the two sorted halves into one sorted list by repeatedly taking the smaller front element. The splitting creates about log n levels, and merging does O(n) work per level, so the total is O(n log n), in the best, average, and worst case alike, which makes merge sort wonderfully predictable.

def merge_sort(a):
    if len(a) <= 1:                 # base case
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 9, 1, 7]))   # [1, 2, 5, 7, 9]

The cost of that guarantee is memory: merging builds new lists, so merge sort uses O(n) auxiliary space. It is also stable.

Quicksort

Quicksort picks a pivot element and partitions the list so that everything smaller than the pivot comes before it and everything larger comes after. The pivot is now in its final place; quicksort then recurses on the two sides. With balanced partitions it is O(n log n) on average and typically the fastest sort in practice because it works in place with small constants.

Its weakness is the worst case: O(n^2), which occurs when the pivot is consistently the smallest or largest element (for example, an already-sorted list with a naive first-element pivot), so the partitions are maximally unbalanced. Good implementations avoid this by choosing the pivot randomly or as the median of a few samples, making the worst case extremely unlikely. Quicksort uses O(log n) space on average for its recursion and is usually not stable.

Choosing between them

Sort	Average	Worst	Space	Stable?
Merge sort	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n^2)	O(log n)	No

Use merge sort when you need a guaranteed O(n log n) or a stable sort, or when sorting linked lists. Use quicksort when average speed and low memory matter most. Python's built-in sorted() uses Timsort, a hybrid of merge sort and insertion sort that is O(n log n) and stable.

Binary search finds a target in a sorted array in O(log n) time, a dramatic improvement over the O(n) of scanning every element. It works by repeatedly halving the search range. Compare the target with the middle element: if they match, you are done; if the target is smaller, the answer can only be in the left half; if larger, only in the right half. Each comparison throws away half of what remains.

Why sorted, and why it is fast

Binary search depends entirely on order: only in a sorted array can one comparison with the middle rule out an entire half. Starting from n items, halving repeatedly gives the sequence n, n/2, n/4, and so on down to 1. The number of halvings is about log base 2 of n. Searching a sorted array of a million items takes only about 20 comparisons, versus up to a million for a linear scan.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid            # found it
        elif a[mid] < target:
            lo = mid + 1          # search right half
        else:
            hi = mid - 1          # search left half
    return -1                     # not present

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 9))     # 4
print(binary_search(nums, 4))     # -1

Tracing it

Search for 9 in [1, 3, 5, 7, 9, 11]. Indices 0 to 5, mid = 2, value 5, which is less than 9, so go right: lo becomes 3. Now mid = 4, value 9, match, return 4. Just two comparisons instead of five.

Cost summary

Binary search is O(log n) time. Written iteratively as above it uses O(1) space; written recursively it uses O(log n) stack space. The one requirement is that the data is sorted, so if you will search a collection many times, sorting it once (O(n log n)) to enable fast repeated binary searches is a common and worthwhile trade.

A tree is a hierarchical structure of nodes connected by edges, with no cycles. One node is the root at the top. Each node may have children below it; a node with no children is a leaf. The height of a tree is the number of edges on the longest path from the root down to a leaf. Trees model hierarchy everywhere: file systems, family trees, and the decision structure of many algorithms.

Binary trees

A binary tree restricts each node to at most two children, conventionally called left and right. Here is a node definition:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

The binary search tree property

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This invariant makes search work like binary search: to find a value, compare it with the current node and go left if smaller or right if larger, discarding the other subtree each step.

def bst_insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = bst_insert(root.left, value)
    else:
        root.right = bst_insert(root.right, value)
    return root

def bst_search(root, value):
    if root is None or root.value == value:
        return root
    if value < root.value:
        return bst_search(root.left, value)
    return bst_search(root.right, value)

Complexity depends on shape

Each step down a BST discards one subtree, so search, insert, and delete all cost time proportional to the tree's height. In a balanced BST the height is about log n, giving O(log n) operations. But if you insert already-sorted data into a naive BST, it degenerates into a long chain (essentially a linked list) of height n, giving O(n), the worst case. This is why self-balancing trees such as AVL and red-black trees exist: they perform rotations to keep the height near log n and guarantee O(log n) operations.

Operation	Balanced BST	Unbalanced (worst)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Space is O(n) to store n nodes. A BST keeps data sorted and supports fast ordered operations, filling the gap between the O(1) unordered lookup of a hash table and the ordered-but-static nature of a sorted array.

A traversal visits every node of a tree exactly once in a defined order. There are two families: depth-first traversals that plunge down one branch before backing up, and breadth-first traversal that sweeps level by level. All visit n nodes, so every traversal is O(n) time.

The three depth-first orders

Depth-first traversals differ only in when they visit the current node relative to its subtrees:

• In-order: left subtree, then node, then right subtree.
• Pre-order: node, then left subtree, then right subtree.
• Post-order: left subtree, then right subtree, then node.

def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value)      # visit between the two subtrees
    in_order(node.right)

def pre_order(node):
    if node is None:
        return
    print(node.value)      # visit before the subtrees
    pre_order(node.left)
    pre_order(node.right)

def post_order(node):
    if node is None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.value)      # visit after the subtrees

The special power of in-order

Running an in-order traversal on a binary search tree visits the values in sorted ascending order. This is a direct consequence of the BST property: everything to the left is smaller, everything to the right is larger, so visiting left, node, right yields increasing values. It is a clean way to print a BST in order.

Level-order traversal

Level-order traversal visits all nodes at depth 0, then depth 1, and so on, top to bottom and left to right. Unlike the depth-first orders, it is not naturally recursive; you implement it with a queue: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. This is exactly breadth-first search applied to a tree, which we generalize to graphs in the next module.

Traversal	Order visited	Common use
In-order	Left, node, right	Print a BST in sorted order
Pre-order	Node, left, right	Copy or serialize a tree
Post-order	Left, right, node	Delete a tree or evaluate expressions
Level-order	By depth, using a queue	Shortest path in an unweighted tree

A heap is a specialized binary tree that keeps the most extreme element instantly reachable. In a min-heap, every parent is less than or equal to its children, so the smallest element is always at the root. A max-heap is the mirror image, with the largest at the root. Note that a heap is only partially ordered: unlike a BST, siblings have no required order, which is why a heap cannot search for an arbitrary value quickly, but can always hand you the minimum (or maximum) in O(1).

Shape and array storage

A binary heap is a complete binary tree: every level is full except possibly the last, which fills left to right. This regular shape lets a heap be stored compactly in a plain array with no pointers: the children of index i live at indices 2i + 1 and 2i + 2, and the parent at (i - 1) // 2. That is why heaps are both fast and memory-efficient.

Priority queues

A priority queue is an abstract structure that always removes the highest-priority item next, rather than the oldest (a plain queue) or the newest (a stack). Heaps are the standard way to implement one. Python's heapq module provides a min-heap over a list.

import heapq
pq = []
heapq.heappush(pq, 5)     # insert, O(log n)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
print(pq[0])              # peek smallest -> 1, O(1)
print(heapq.heappop(pq))  # extract smallest -> 1, O(log n)
print(heapq.heappop(pq))  # -> 3

How the operations work and cost

To insert, place the new element at the end of the array and let it "bubble up," swapping with its parent while it is smaller. To extract the root, move the last element to the root and let it "sink down," swapping with its smaller child until the heap property is restored. Both traverse at most the height of the tree, which is log n, so both are O(log n). Peeking at the minimum is just reading the root, O(1).

Operation	Complexity
Peek min/max (root)	O(1)
Insert (push)	O(log n)
Extract min/max (pop)	O(log n)

Heaps power task schedulers, Dijkstra's shortest-path algorithm, and the heapsort algorithm (build a heap, then repeatedly extract the min for an O(n log n) sort). Space is O(n).

A graph is the most general way to model relationships: a set of vertices (nodes) connected by edges (links). Unlike a tree, a graph may contain cycles, may be disconnected, and places no limit on how vertices connect. Graphs model road maps, social networks, web pages and links, prerequisites, and computer networks. Trees, in fact, are just a special case of graphs (connected and acyclic).

Varieties of graph

• Undirected: edges have no direction; a friendship link goes both ways.
• Directed (digraph): edges point one way, like a one-way street or a "follows" relationship.
• Weighted: each edge carries a number, such as distance or cost.
• Unweighted: edges simply exist or not.

Two ways to store a graph

The representation you choose affects both memory and speed. The two standard choices are the adjacency list and the adjacency matrix. Let V be the number of vertices and E the number of edges.

An adjacency list stores, for each vertex, a list of its neighbors. It uses O(V + E) space, which is efficient for sparse graphs (few edges), the common real-world case.

# Adjacency list as a dict of neighbor lists
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}
print(graph["A"])   # neighbors of A: ['B', 'C']

An adjacency matrix is a V by V grid where cell [i][j] is 1 (or the weight) if an edge runs from i to j, and 0 otherwise. Checking whether two specific vertices are connected is O(1), but it always uses O(V squared) space regardless of how few edges exist, which is wasteful for sparse graphs.

Representation	Space	Check edge (u,v)	Best for
Adjacency list	O(V + E)	O(degree of u)	Sparse graphs
Adjacency matrix	O(V^2)	O(1)	Dense graphs

Most practical graphs are sparse, so the adjacency list is the usual default, and it is what the traversal algorithms in the next lesson assume.

Once a graph is built, the fundamental task is to traverse it: systematically visit vertices reachable from a start. The two core strategies are breadth-first search and depth-first search. Both visit every reachable vertex and every edge once, so both run in O(V + E) time with an adjacency list. The crucial detail in a graph (unlike a tree) is that cycles exist, so you must track visited vertices to avoid looping forever.

Breadth-first search (BFS)

BFS explores in expanding rings: it visits the start, then all neighbors, then all their unvisited neighbors, and so on. It uses a queue (FIFO). Because it fans out level by level, BFS discovers vertices in order of their distance from the start, which is why BFS finds the shortest path in an unweighted graph (fewest edges).

from collections import deque

def bfs(graph, start):
    visited = set([start])
    q = deque([start])
    order = []
    while q:
        node = q.popleft()     # dequeue (FIFO)
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                q.append(nbr)
    return order

Depth-first search (DFS)

DFS plunges as deep as possible along one path before backtracking. It uses a stack (LIFO), either explicitly or via the recursion call stack. DFS is the natural choice for detecting cycles, finding connected components, topological sorting, and exploring mazes.

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for nbr in graph[node]:
        if nbr not in visited:
            dfs(graph, nbr, visited, order)   # recurse deeper
    return order

Choosing between them

	BFS	DFS
Data structure	Queue (FIFO)	Stack / recursion (LIFO)
Order	By distance from start	Deep along a path first
Shortest path (unweighted)?	Yes	Not guaranteed
Time	O(V + E)	O(V + E)

Both use O(V) extra space for the visited set (and the queue or recursion stack). The rule of thumb: use BFS when you need the shortest path in an unweighted graph or want to search nearest-first; use DFS when you need to exhaustively explore, detect cycles, or the solution is likely deep. For weighted shortest paths you would move on to Dijkstra's algorithm, which uses the priority queue you met in the previous module.