Trees and Graphs

1Binary tree shape

A binary tree gives every node at most two children, conventionally left and right. With n nodes there are exactly n - 1 edges — one parent link into each non-root — so the structure is connected and acyclic by construction. Height h is the longest root-to-leaf path in edges; a complete filling of levels keeps h = \lfloor \log_2 n \rfloor, while a chain of nodes pushes h to n - 1. Unused null child slots are not edges.

Figure. Five-node binary tree. Four parent→child edges; C is a leaf with no children drawn.

What the shape guarantees

1. At most two childrenEach node may have a left child, a right child, both, or neither — never a third sibling under the same parent.
2. Tree edge countEvery node except the root has exactly one parent edge, so n nodes imply n - 1 edges.
3. Height bounds costAny root-to-leaf walk is at most h edges; algorithms that follow child pointers once per level cost O(h).

2BST order and O(h) search

A binary search tree strengthens the binary tree with an order rule: every key in the left subtree is strictly smaller than the node, and every key in the right subtree is strictly larger. Search, insert and delete then follow one child per level, so each costs O(h). That is O(\log n) when the tree stays balanced and O(n) when it degenerates into a chain — the asymptotic label is height, not a free log-n guarantee.

Figure. Same BST as the worked example. Left subtree of 8 holds {1,3,6}; right holds {10}.

Search for a key

1. Start at the rootCompare the target with the current key.
2. Branch onceGo left if the target is smaller, right if larger; stop if equal.
3. Miss ends at nullA null child means the key is absent; insert would hang a new node there.

3In-order, pre-order, post-order

Three depth-first walks differ only in when they record the node relative to its subtrees: in-order is left, node, right; pre-order is node, left, right; post-order is left, right, node. In-order of a BST is sorted order — that is the walk for validating a BST or finding the k-th smallest. Pre-order is the natural order to copy or serialise a tree; post-order deletes children before the parent.

Walk the five-key tree from BST order and O(h) search: in-order emits left, node, right (sorted keys); pre-order emits node first; post-order emits the node after both children.

Recursive in-order

1. Go leftFully traverse the left subtree first.
2. VisitRecord the current node's key.
3. Go rightFully traverse the right subtree.

In-order, recursive

def inorder(node, out):
    if not node:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

4Level-order traversal

Level order visits a binary tree breadth-first: every node at depth d before any node at depth d+1, left to right within a level. The iterative form keeps a queue; the one move that separates levels is recording the queue's length at the start of each pass and draining exactly that many nodes. That is still O(n) time and O(n) queue space in the worst case — a complete level can hold \Theta(n) nodes — and it is the same BFS that finds shortest paths in an unweighted graph.

Figure. Same tree as the worked example. BFS drains depth 0, then depth 1, then depth 2 — never a child before every node on its parent's level.

How it works

1. Seed the queuePush the root. An empty tree yields an empty list of levels and stops here.
2. Freeze the widthAt the start of a pass, set width = length(queue). Those nodes are exactly the current level.
3. Drain and expandDequeue width nodes, append each value to this level, and enqueue each existing left then right child.
4. Emit the levelAppend the collected level to the answer and loop while the queue still holds the next depth.

Level order, iterative

from collections import deque

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        width = len(q)
        level = []
        for _ in range(width):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

5Adjacency list vs matrix

A graph stores vertices and the edges between them. An adjacency list keeps, for each vertex, the neighbors it touches — O(V + E) space and a natural fit for sparse graphs. An adjacency matrix is a V \times V table with a bit (or weight) per ordered pair — O(V^2) space and O(1) edge existence checks, which pays off only when the graph is dense or you query edges constantly. Prefer the list for sparse graphs (most real graphs); reach for the matrix only when density or constant-time edge tests demand it.

Figure. Sparse graphs favour adjacency lists; dense graphs or O(1) edge tests favour a matrix.

Pick a representation

1. Count densityIf E is far below V^2, a list wastes less space and iterates only real edges.
2. Need edge tests?Matrix answers "is (u,v) an edge?" in O(1); a list may scan u's neighbor array.
3. Default for interviewsBuild a list (or dict of lists) unless the problem states a dense graph or needs constant-time edge queries.

6BFS shortest path (unweighted)

Breadth-first search explores a graph level by level with a queue, marking vertices as visited so each is enqueued once. In an unweighted graph (every edge cost 1), the first time BFS reaches a vertex is along a shortest path, so distances are final when dequeued. That is O(V + E) time and O(V) queue/visited space. Shortest path in an unweighted graph is BFS, not DFS — DFS can reach a far vertex down a long path before it ever sees a short one.

Figure. Same graph as the worked example. Node labels show BFS hop distance from A.

Distance BFS from s

1. SeedSet dist[s] = 0, enqueue s, mark visited.
2. ExpandDequeue u; for each unvisited neighbor v set dist[v] = dist[u] + 1, mark visited, enqueue v.
3. StopWhen the queue empties, every reachable vertex has its hop distance; unreachable stay unset.

Unweighted distances

from collections import deque

def bfs_dist(graph, s):
    dist = {s: 0}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Coding lab. BFS hops from A runs in the app, with checks on your output.

7DFS: deepen, then backtrack

Depth-first search pushes as far as possible along one path before backtracking, using the call stack (recursion) or an explicit stack. Like BFS it runs in O(V + E) and marks vertices so each is expanded once. DFS is the usual tool when the question is about structure along a path — cycle detection in directed or undirected graphs, connected components, and (on a DAG) finishing-time order for a topological sort. It is not the tool for unweighted shortest paths.

Figure. DFS deepens then backtracks — right tool for structure along a path (cycles, components, finish-time topo). Unweighted shortest paths stay with BFS.

Recursive DFS from u

1. MarkMark u visited as you enter.
2. RecurseFor each unvisited neighbor v, recurse on v (or push v on an explicit stack).
3. FinishWhen every neighbor is done, u is finished — finish times feed topological order on a DAG.

DFS mark

def dfs(u, graph, seen):
    seen.add(u)
    for v in graph[u]:
        if v not in seen:
            dfs(v, graph, seen)

8Number of islands

A grid of land ('1') and water ('0') is a graph in disguise: each land cell is a vertex with up to four edges to orthogonal land neighbors. The number of islands is the number of connected components of land. Scan every cell; when you hit an unvisited '1', increment the count and run DFS or BFS to mark the whole component visited. Total work is O(\textit{rows} \times \textit{cols}) — each cell is entered a constant number of times.

Figure. Same 3×3 grid as the worked example. The top-left land blob is one 4-connected component; the bottom-right 1 is a second.

Count components

1. ScanWalk every cell left-to-right, top-to-bottom.
2. LaunchOn an unvisited land cell, add 1 to the island count.
3. FloodDFS or BFS from that cell, marking every 4-reachable land cell visited (often by flipping '1' to '0').
4. ContinueResume the scan; already-marked land is skipped. Launches equal islands.

Islands via DFS flood

def num_islands(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])

    def flood(r, c):
        if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    islands = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                islands += 1
                flood(r, c)
    return islands