Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

A single depth-first search (DFS), augmented with a discovery-time array disc (when each vertex was first visited) and a low-link array low (the earliest discovery time reachable from that vertex's subtree using at most one edge that isn't a tree edge), finds articulation points and bridges in an undirected graph in $O(V + E)$. A structurally similar DFS, but with an explicit stack of "in-progress" vertices and using directed edges, finds strongly connected components (SCCs, maximal clusters where every node can reach every other node in the cluster) in a directed graph, also in $O(V + E)$. Both share the low-link idea and both do exactly one DFS, but they are not literally the same pass on the same graph: articulation points and bridges are an undirected-graph question, and strongly connected components is a directed-graph question, so which one applies depends on whether you're treating your edges as two-way or one-way.

Structured elaboration

Undirected graphs: articulation points and bridges

disc[v] is v's DFS visit order. low[v] is defined as:

$\text{low}[u] = \min\big(\text{disc}[u],\ \min_{w:(u,w)\text{ back-edge}} \text{disc}[w],\ \min_{v:(u,v)\text{ tree-edge}} \text{low}[v]\big)$

that is, the earliest thing u's own subtree can reach, either directly (a back edge straight to an ancestor) or through one of its DFS-tree children.

• Articulation point rule. The DFS root is an articulation point if and only if it has two or more DFS-tree children (removing it splits those children's subtrees apart). A non-root vertex u is an articulation point if it has a tree-edge child v with $\text{low}[v] \ge \text{disc}[u]$: that child's whole subtree cannot reach anything above u without passing through u itself.
• Bridge rule, same low-link values, a stricter comparison: a tree edge (u, v) is a bridge if $\text{low}[v] > \text{disc}[u]$ (strict): v's subtree cannot reach u or anything above u at all without that one edge, not even u itself.

Directed graphs: strongly connected components

Maintain an explicit stack of vertices currently on the current DFS path, plus an on_stack flag per vertex. The low-link rule changes in one important way: when considering an edge to an already-visited vertex w, you only fold in disc[w] if w is currently on the stack, not merely visited, since a visited-but-popped vertex belongs to an already-finished, unrelated component. When $\text{low}[u] = \text{disc}[u]$ after all of u's edges are explored, u is the root of a complete SCC: pop the stack down through and including u, and everyone popped is that component.

The "module dependency graph" framing maps onto this directly: if nodes are modules and edges are "depends on" relationships, an SCC with more than one node is a circular dependency cluster (module A eventually depends back on itself through some chain); a singleton SCC with no self-loop is a module with no circular dependency at all.

def articulation_points(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v); g[v].append(u)
    disc, low, is_ap, timer = [-1]*n, [0]*n, [False]*n, [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in g[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    is_ap[u] = True
            else:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            is_ap[u] = True

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return sorted(i for i in range(n) if is_ap[i])


def tarjan_scc(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    disc, low, on_stack, stack, timer, sccs = [-1]*n, [0]*n, [False]*n, [], [0], []

    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        stack.append(u); on_stack[u] = True
        for v in g[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            comp = []
            while True:
                w = stack.pop(); on_stack[w] = False; comp.append(w)
                if w == u:
                    break
            sccs.append(sorted(comp))

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs


bowtie_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
print(articulation_points(5, bowtie_edges))

directed_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]
print(tarjan_scc(6, directed_edges))

Worked example

For an undirected "bowtie" (two triangles sharing one vertex): edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,2), articulation_points(5, edges) returns [2], the shared vertex, since removing it disconnects the two triangles from each other.

For a directed graph modeling module dependencies with two independent cyclic clusters bridged by one one-way dependency: edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3), tarjan_scc(6, edges) returns [[3, 4, 5], [0, 1, 2]]: two separate circular-dependency clusters (modules 0-1-2 and modules 3-4-5), connected only by the one-way edge from module 2 into module 3, so they are two SCCs, not one.

Complexity

Both articulation_points and tarjan_scc do a single DFS: the disc[i] == -1 guard means
each vertex is visited, and gets its dfs call, exactly once, so the outer loop plus all dfs
calls together do $O(V)$ work setting up and finishing each vertex. Inside dfs, the for v in g[u] loop examines each entry of each vertex's adjacency list exactly once; summed over
every vertex, that is $O(E)$ total (an undirected edge appears in two adjacency lists, still
$O(E)$ with a constant factor of 2). So total time is $O(V + E)$. Space is $O(V)$ for
disc/low/is_ap (or on_stack), plus $O(V)$ for the explicit stack (Tarjan's SCC) or the
recursion call stack (both algorithms), plus $O(V + E)$ for the adjacency-list representation
itself.

Edge cases

• Disconnected graph: the outer for i in range(n): if disc[i] == -1: dfs(i, -1) restarts
  DFS from every unvisited vertex, so each component gets its own DFS tree and its own
  root-special-case check.
• Self-loop ((u, u)) in articulation_points: g[u] gets u appended to it (from both
  sides of the edge); when dfs scans that entry, disc[u] is already set (to u's own
  discovery time) before the loop starts, so it falls into the else branch
  (low[u] = min(low[u], disc[u])), a harmless no-op since disc[u] can never be smaller than
  the low[u] it was initialized to.
• Single-vertex graph (n=1, no edges): dfs(0, -1) has no neighbors, children=0, so the
  root special case (children > 1) is false; articulation_points returns [] and
  tarjan_scc returns the single component [[0]].
• Empty graph (n=0): both outer loops run zero times, so both functions return [].
• Parallel edges between the same undirected pair: also flagged in Trade-offs below as
  breaking the naive "skip the parent by vertex id" rule, since it wrongly treats one of the
  parallel edges as a back edge to an ancestor.

Trade-offs & pitfalls

• The root special case is the most common articulation-point bug: the DFS root needs two or more tree-edge children, not just "has a child," to count as an articulation point.
• Bridge vs. articulation-point comparisons are easy to swap: bridges use the strict low[v] > disc[u], articulation points use the non-strict low[v] >= disc[u]. Mixing the two up silently misclassifies edges as bridges (or vertices as articulation points) that aren't.
• Parallel edges break the naive "skip the parent" rule for undirected graphs: if there are two edges between the same pair of vertices, skipping any edge back to parent by vertex id alone will wrongly treat one of the parallel edges as a back edge to an ancestor; tracking edge identity (not just the parent vertex) fixes this.
• For SCCs, checking disc[w] for any visited w instead of only vertices currently on_stack is a bug that silently merges vertices from different, already-finished DFS branches into the same low-link value, producing wrong components.
• Kosaraju's algorithm is the classic alternative for SCCs: two full DFS passes, one over the graph and one over its transpose, which is easier to reason about but costs an explicit graph transpose and a second full traversal, versus Tarjan's single pass with a stack.

Direct answer

Put every element into a hash set, then only start "walking" a run from numbers that are the start of a run, meaning their predecessor (x - 1) is not in the set. From each such start, walk forward through x+1, x+2, ... while each is present, and track the longest walk seen. Because a hash set gives $O(1)$ average membership checks and every element is only ever walked once across the whole algorithm, this runs in average $O(n)$ time without sorting.

Structured elaboration

Approach. Sorting first would cost $O(n \log n)$, which is worse than the $O(n)$ bound the problem asks for; the hash set gets you constant-time "is this the start of a run" and "is the next number present" checks that a sorted array cannot beat once you account for the sort itself.

def longest_consecutive(nums):
    """
    Return length of longest consecutive sequence in nums.
    Average O(n) time, O(n) space.
    """
    if not nums:
        return 0
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:          # only start counting at a run's beginning
            length = 1
            cur = x + 1
            while cur in s:
                length += 1
                cur += 1
            best = max(best, length)
    return best

Why the x - 1 not in s check keeps it linear. Without it, every element would try to walk its own run, redoing the same work as its predecessors: for a run of length L you'd do $1 + 2 + \dots + L = O(L^2)$ work instead of $O(L)$. The start-of-run check means the inner while loop only ever fires from a true run start, and every element is visited by exactly one such walk (the one belonging to its run), so total inner-loop work across the whole array is bounded by n, not by the number of runs times their lengths.

Worked example

nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums))

Output: 4

Trace: the set is {100, 4, 200, 1, 3, 2}. Only 100 (no 99), 200 (no 199), and 1 (no 0) are run starts. From 1: 2, 3, 4 are all present, giving a run of length 4 (1,2,3,4). From 100 and 200: no successor present, so length 1 each. The longest is 4.

Trade-offs & pitfalls

Key points

• Sorting-based solutions (sort, then scan for consecutive runs) are simpler to reason about and use no extra hash-set memory, but they cost $O(n \log n)$ from the sort itself, which is asymptotically worse than the hash-set approach for large n.
• The hash-set approach only pays off because you resist the temptation to walk a run from every element; the "start of run" gate is what keeps total work linear instead of quadratic in the worst case (e.g., one giant consecutive run).
• Average-case linear time relies on the hash set having O(1) average operations; under adversarial hash collisions (a concern in security-sensitive contexts) a hash set's worst case degrades, whereas sorting's $O(n \log n)$ worst case is guaranteed regardless of input.

Complexity

• Time: average $O(n)$ (building the set is O(n); every element is visited by the inner while loop at most once across the whole run).
• Space: $O(n)$ for the hash set.

Edge cases

• Empty array: returns 0 immediately.
• Duplicates: the set naturally deduplicates, so [1, 2, 2, 3] still returns a run length of 3, not 4.
• All elements identical: every element is its own non-start except one value, giving a run length of 1.
• Negative numbers or gaps: the algorithm works unchanged since it relies only on integer successor relationships, not on sign or magnitude.

Direct answer

Pick based on two properties of the graph and one property of the query: if every edge has the same weight, breadth-first search (BFS) alone gives shortest paths in linear time; if weights differ but are never negative, Dijkstra's algorithm is the standard single-source choice; if a negative weight is possible (but no negative cycle), Dijkstra can give a wrong answer and Bellman-Ford is required instead; and if you need distances between every pair rather than from one source, Floyd-Warshall (a dynamic-programming algorithm that considers every node in turn as a possible shortcut between every pair) is the natural fit for all-pairs, or equivalently running Dijkstra from every node. A* only changes single-source, non-negative-weight search: it adds a heuristic estimate of remaining distance to prioritize expansion toward a specific goal, and it only helps, versus plain Dijkstra, when that heuristic is admissible (it never overestimates the true remaining cost), since an inadmissible heuristic can cause A* to return a path that is not actually shortest.

Structured elaboration

Decision order:

1. Are all edge weights equal (or is the graph unweighted)? Use BFS: $O(V + E)$, no priority queue needed at all.
2. Do you need distances between every pair of nodes, not just from one source? Use Floyd-Warshall, $O(V^3)$, or repeat Dijkstra from every source if the graph is sparse and there are no negative weights.
3. Otherwise, single-source with weights: are negative edge weights possible? If yes, use Bellman-Ford, $O(V \cdot E)$, which also detects a negative cycle if one exists (a cycle whose total weight is negative, which makes "shortest path" undefined, since you could loop it forever to keep decreasing the cost). If no, use Dijkstra, $O((V+E) \log V)$ with a binary heap.
4. If you additionally have a single, known goal node (not "distances to everywhere"), and a decent estimate of remaining distance, layer A* on top of Dijkstra's non-negative-weight assumption to reduce how much of the graph gets explored.

Why Dijkstra breaks under negative weights: once Dijkstra pops a node off its priority queue, it treats that node's distance as final and never revisits it, on the assumption that nothing already queued could possibly offer a shorter path, since all remaining edges only add non-negative weight. A negative edge violates that assumption directly: a longer-looking path discovered later can still turn out shorter once a negative edge is added to it.

What A's heuristic must guarantee*: admissibility, never overestimating the true remaining cost to the goal. Given an admissible heuristic, A* is guaranteed to still find a shortest path, exactly like Dijkstra, but it explores fewer nodes when the heuristic is informative, because it prioritizes nodes that look closer to the goal rather than merely closer to the start. (A stronger property, consistency, additionally guarantees a node is never re-expanded after being finalized, which is what lets A* implementations skip the "revisit and relax an already-closed node" bookkeeping that a merely admissible-but-inconsistent heuristic would otherwise require.) A straight-line (Euclidean) distance heuristic on a road network or grid is a classic admissible choice, since no real route can be shorter than the straight line.

Worked example

Bellman-Ford correctness under a negative edge, where Dijkstra gets it wrong:

import math

def dijkstra(adj, src):
    import heapq
    dist = {src: 0}
    finalized = set()
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in finalized:
            continue
        finalized.add(u)
        for v, w in adj.get(u, []):
            if v in finalized:
                continue
            nd = d + w
            if nd < dist.get(v, math.inf):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def bellman_ford(edges, nodes, src):
    dist = {n: math.inf for n in nodes}
    dist[src] = 0
    for _ in range(len(nodes) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected")
    return dist

# True shortest A->B is via C: 1 -> 4 + (-10) = -6, but Dijkstra finalizes
# B at distance 1 (direct edge) before C is even processed.
adj = {"A": [("B", 1), ("C", 4)], "C": [("B", -10)]}
edges = [("A", "B", 1), ("A", "C", 4), ("C", "B", -10)]
nodes = ["A", "B", "C"]

print("dijkstra:", dijkstra(adj, "A"))
print("bellman_ford:", bellman_ford(edges, nodes, "A"))

Running this prints:

dijkstra: {'A': 0, 'B': 1, 'C': 4}
bellman_ford: {'A': 0, 'B': -6, 'C': 4}

Dijkstra reports B at distance 1 (wrong: it finalized B via the direct edge before discovering the cheaper route through C), while Bellman-Ford correctly finds -6 via A to C to B.

A exploring fewer nodes than Dijkstra given an admissible heuristic*, on an open 20x20 grid from (0,0) to (5,5), using Manhattan distance as the heuristic:

import heapq

def neighbors(pos, size):
    x, y = pos
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < size and 0 <= ny < size:
            yield (nx, ny)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def search(start, goal, size, use_heuristic):
    h = (lambda n: manhattan(n, goal)) if use_heuristic else (lambda n: 0)
    g = {start: 0}
    pq = [(h(start), start)]
    visited = set()
    expansions = 0
    while pq:
        _, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        expansions += 1
        if node == goal:
            break
        for nb in neighbors(node, size):
            ng = g[node] + 1
            if ng < g.get(nb, float("inf")):
                g[nb] = ng
                heapq.heappush(pq, (ng + h(nb), nb))
    return g[goal], expansions

size = 20
start, goal = (0, 0), (5, 5)
dist_astar, exp_astar = search(start, goal, size, use_heuristic=True)
dist_dij, exp_dij = search(start, goal, size, use_heuristic=False)
print("A* distance:", dist_astar, "nodes expanded:", exp_astar)
print("Dijkstra distance:", dist_dij, "nodes expanded:", exp_dij)

Running this prints:

A* distance: 10 nodes expanded: 36
Dijkstra distance: 10 nodes expanded: 61

Both find the same correct shortest distance (10), but A* reaches it having expanded 36 nodes against Dijkstra's 61, because the heuristic steered expansion toward the goal instead of outward in every direction equally.

Trade-offs & pitfalls

A common mistake is treating A* as "a different algorithm" from Dijkstra rather than as Dijkstra with a heuristic added to the priority; with a heuristic of zero everywhere (as in the comparison above), A* degenerates to exactly Dijkstra, which is a good way to check an A* implementation for bugs. A second pitfall is picking a heuristic that overestimates in some region "because it prunes more nodes": an inadmissible heuristic can make A* return a path that is not actually shortest, so any heuristic must be checked against the admissibility property, not just judged by how much it speeds things up. Practically, Dijkstra's own implementation constant matters too: with a binary heap, each edge relaxation that improves a distance costs $O(\log V)$ to sift, which under many decrease-key-style relaxations is the dominant cost; the common fix is not switching to a Fibonacci or pairing heap (both have amortized $O(1)$ or near-$O(1)$ decrease-key but carry higher constant factors and more complex implementations) but instead allowing duplicate, stale entries in a plain binary heap and lazily discarding them on pop, which is what the Dijkstra implementation above already does and is the standard practical choice.

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.

Direct answer

Huffman coding is optimal among prefix-free codes because repeatedly merging the two lowest-frequency nodes builds the encoding tree bottom-up in exactly the order that minimizes total weighted path length (each symbol's frequency times its code length, summed over all symbols). Merging any other pair first can strand a frequent symbol deeper than it needs to be, which strictly increases the encoded size.

Structured elaboration

Build procedure: put every symbol in a min-heap keyed by frequency; while more than one node remains, pop the two smallest, create a parent whose frequency is their sum, and push it back; the last remaining node is the tree's root. Assigning 0/1 to left/right edges yields prefix-free codes, since every symbol sits at a distinct leaf.

import heapq
from collections import Counter

def build_huffman_codes(freqs: dict[str, int]) -> dict[str, str]:
    """
    freqs: symbol -> frequency (must have >= 2 distinct symbols).
    Returns symbol -> binary code string.
    """
    if len(freqs) < 2:
        raise ValueError("need at least 2 distinct symbols for a prefix tree")

    counter = 0
    heap = []
    for sym, f in freqs.items():
        heapq.heappush(heap, (f, counter, sym))
        counter += 1

    while len(heap) > 1:
        f1, _, n1 = heapq.heappop(heap)
        f2, _, n2 = heapq.heappop(heap)
        merged = (n1, n2)
        heapq.heappush(heap, (f1 + f2, counter, merged))
        counter += 1

    _, _, root = heap[0]
    codes: dict[str, str] = {}

    def walk(node, prefix):
        if isinstance(node, tuple):
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
        else:
            codes[node] = prefix or "0"  # single-symbol edge case

    walk(root, "")
    return codes


def encoded_length_bits(freqs: dict[str, int], codes: dict[str, str]) -> int:
    return sum(freqs[s] * len(codes[s]) for s in freqs)


message = "abracadabra"
freqs = dict(Counter(message))
print("frequencies:", freqs)

codes = build_huffman_codes(freqs)
for s in sorted(codes, key=lambda s: (-freqs[s], s)):
    print(f"  {s!r}: freq={freqs[s]} code={codes[s]} (len {len(codes[s])})")

huff_bits = encoded_length_bits(freqs, codes)
fixed_bits = len(message) * 3  # 5 distinct symbols -> ceil(log2(5)) = 3 bits fixed-width
print(f"Huffman total bits: {huff_bits}")
print(f"Fixed-width (3 bits/symbol) total bits: {fixed_bits}")

Output:

frequencies: {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
  'a': freq=5 code=0 (len 1)
  'b': freq=2 code=110 (len 3)
  'r': freq=2 code=111 (len 3)
  'c': freq=1 code=100 (len 3)
  'd': freq=1 code=101 (len 3)
Huffman total bits: 23
Fixed-width (3 bits/symbol) total bits: 33

Why the greedy order is optimal (exchange argument sketch): take any optimal prefix tree. Among its deepest leaves, if the two globally-lowest-frequency symbols aren't already siblings there, swap them into those two deepest sibling positions; that swap can only lower or keep equal the total weighted path length, since moving a low-frequency symbol deeper (and a higher-frequency one shallower) never increases the frequency-times-depth sum. So an optimal tree with this sibling property always exists. Once those two symbols are fixed as siblings, merge them into one "super-symbol" of combined frequency; the same greedy step is optimal on the resulting (n-1)-symbol problem by induction, which is exactly what "always merge the two smallest" does at every level.

What breaks with a different merge order: merging arbitrary (not-lowest) nodes can pull a high-frequency symbol away from the root and bury it several merge levels deep before anything forces it back up, inflating its code length instead of shrinking it.

Worked example

For the weighted path length $\text{WPL}(T) = \sum_{s \in \Sigma} f(s)\cdot \text{depth}_T(s)$, applying the wrong merge rule (always combining the two LARGEST nodes first, instead of the two smallest) to the same "abracadabra" frequencies produces a tree whose weighted path length is 37 bits, worse than the fixed-width 33-bit baseline and far worse than the correct Huffman tree's 23 bits: the frequent symbol 'a' (frequency 5) gets buried under extra merges instead of staying near the root.

import heapq

freqs = {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

def weighted_path_length(node, depth=0):
    if isinstance(node, tuple):
        return (weighted_path_length(node[0], depth + 1)
                + weighted_path_length(node[1], depth + 1))
    return freqs[node] * depth

# Correct order: merge the two SMALLEST nodes each step (standard Huffman).
counter = 0
heap = [(f, i, s) for i, (s, f) in enumerate(freqs.items())]
counter = len(heap)
heapq.heapify(heap)
while len(heap) > 1:
    f1, _, n1 = heapq.heappop(heap)
    f2, _, n2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, counter, (n1, n2)))
    counter += 1
_, _, optimal_root = heap[0]
print("optimal weighted path length (bits):", weighted_path_length(optimal_root))

# Bad order: at each step, merge the two HIGHEST-frequency nodes instead.
counter = 0
heap2 = [[f, i, s] for i, (s, f) in enumerate(freqs.items())]
counter = len(heap2)
while len(heap2) > 1:
    heap2.sort(key=lambda x: -x[0])  # sort descending, take two largest
    f1, _, n1 = heap2.pop(0)
    f2, _, n2 = heap2.pop(0)
    heap2.append([f1 + f2, counter, (n1, n2)])
    counter += 1
_, _, bad_root = heap2[0]
print("bad-order (merge two largest first) weighted path length (bits):", weighted_path_length(bad_root))

Output:

optimal weighted path length (bits): 23
bad-order (merge two largest first) weighted path length (bits): 37

Complexity

Building the tree is $O(n \log n)$ for $n$ distinct symbols ($n-1$ heap merges, each
$O(\log n)$); encoding a message of length $m$ is $O(m)$; memory is $O(n)$ for the
tree/codebook.

Edge cases

• Ties in frequency: any tie-break among equally-small nodes preserves the optimal total
  length (though it can change WHICH codeword a given symbol gets); canonical Huffman fixes a
  deterministic tie-break so encoder and decoder agree, which matters for decodability, not for
  optimality itself.
• Single-symbol alphabet is a degenerate edge case: assign a length-1 code by convention,
  since there is nothing to disambiguate.
• Fewer than 2 distinct symbols: build_huffman_codes explicitly raises ValueError when
  len(freqs) < 2, since a prefix tree needs at least two leaves to have anything to
  disambiguate.

Trade-offs & pitfalls

• Static vs adaptive: this build requires knowing (or transmitting) the frequency table up front; if the true distribution drifts mid-stream, adaptive Huffman (the Vitter algorithm) or arithmetic/range coding track a moving distribution without a fixed prior codebook, at the cost of more per-symbol bookkeeping.
• Where Huffman itself falls short: Huffman is optimal only among prefix codes with INTEGER-length codewords per symbol; a symbol with true probability 0.9 "wants" roughly 0.15 bits under the Shannon bound, but no prefix code can give any symbol fewer than 1 bit. For very skewed, single-dominant-symbol distributions, arithmetic or range coding packs closer to the entropy bound than Huffman ever can.