Graphs and trees

Graphs are the single highest-leverage topic in an algorithms interview, because a large fraction of “real” problems are graph problems in disguise — dependencies, state machines, grids, word ladders, course schedules, currency arbitrage, package resolution. Trees are the special case with no cycles, where the algorithms simplify enough that you should be able to write them without thinking.

Every algorithm here was executed. Where two algorithms solve the same problem (Kahn vs DFS topological sort, Prim vs Kruskal, Tarjan vs Kosaraju) the tests check that they agree, which is a much stronger signal than checking one against a hand-computed answer.

Representations and the Graph classes are in Data structures: TypeScript §18 and Python §21.

Table of contents

• 1. Vocabulary and the algorithm chooser
• 2. BFS and DFS
• 3. Grids as graphs
• 4. Topological sort
• 5. Cycle detection
• 6. Shortest paths
• 7. Minimum spanning trees
• 8. Strongly connected components
• 9. Bipartite graphs, colouring, and matching
• 10. Trees: the core operations
• 11. Tree techniques worth naming
• 12. Test run
• 13. Interview questions

1. Vocabulary and the algorithm chooser

The chooser

The single most common mistake: reaching for Dijkstra when the graph is unweighted. BFS is simpler, faster, and correct. Dijkstra with all-equal weights is BFS with unnecessary overhead.

2. BFS and DFS

graph TD
    N1["1<br/>BFS: 1st, DFS: 1st"]
    N2["2<br/>BFS: 2nd, DFS: 2nd"]
    N3["3<br/>BFS: 3rd, DFS: 5th"]
    N4["4<br/>BFS: 4th, DFS: 3rd"]
    N5["5<br/>BFS: 5th, DFS: 4th"]
    N1 --> N2
    N1 --> N3
    N2 --> N4
    N3 --> N4
    N4 --> N5

The diamond at node 4 (reachable from both 2 and 3) is why marking a vertex visited on enqueue matters: BFS visits it once, in level order (1,2,3,4,5), while DFS dives all the way down one branch before backtracking to the other (1,2,4,5,3).

from collections import defaultdict, deque

def bfs(adj, s):
    """Level-by-level. Visits in non-decreasing distance order -> shortest paths for free."""
    seen = {s}; q = deque([s]); order = []
    while q:
        v = q.popleft()                       # popleft, NOT pop(0) — see the complexity note below
        order.append(v)
        for n in adj[v]:
            if n not in seen:
                seen.add(n)                   # mark on ENQUEUE, not on dequeue
                q.append(n)
    return order

def bfs_levels(adj, s):
    """Distances in edges. This is the whole reason BFS exists."""
    seen = {s}; q = deque([s]); dist = {s: 0}
    while q:
        v = q.popleft()
        for n in adj[v]:
            if n not in seen:
                seen.add(n); dist[n] = dist[v] + 1; q.append(n)
    return dist

def dfs_rec(adj, s, seen=None, order=None):
    if seen is None: seen, order = set(), []
    seen.add(s); order.append(s)
    for n in adj[s]:
        if n not in seen: dfs_rec(adj, n, seen, order)
    return order

def dfs_iter(adj, s):
    """Iterative DFS. Note `reversed` so the visit order matches the recursive version."""
    seen = set(); st = [s]; order = []
    while st:
        v = st.pop()
        if v in seen: continue                # a vertex can be pushed multiple times
        seen.add(v); order.append(v)
        for n in reversed(adj[v]):
            if n not in seen: st.append(n)
    return order

Verified: on the same graph, bfs gives [1,2,3,4,5], both DFS variants give [1,2,4,5,3], and bfs_levels gives {1:0, 2:1, 3:1, 4:2, 5:3}.

The three details that matter

1. Mark visited on enqueue, not on dequeue. If you mark when you pop, a vertex reachable from several places gets pushed several times before any of them is processed, and the queue can grow to O(E). Correctness survives; complexity does not.

2. Never q.pop(0) / arr.shift(). Both are O(n), turning an O(V+E) BFS into O(V^2). Measured at 145x slower on 32,000 elements in Complexity §9.1. Use collections.deque in Python and an index cursor or ring buffer in JavaScript:

// The JS BFS that is actually O(V+E): array as a queue, with a moving read index.
function bfs<T>(adj: Map<T, T[]>, start: T): T[] {
  const seen = new Set([start]);
  const q: T[] = [start];
  const order: T[] = [];
  for (let head = 0; head < q.length; head++) {      // no shift(), no dequeue cost
    const v = q[head]!;
    order.push(v);
    for (const n of adj.get(v) ?? []) if (!seen.has(n)) { seen.add(n); q.push(n); }
  }
  return order;
}

3. Recursive DFS overflows. Python’s default limit is ~1000 frames and V8’s is ~11,000; a 1e5-node path graph blows both. When V can be large, write the iterative version. See Complexity §4.1.

BFS vs DFS

DFS’s edge classification is what makes it the right tool for cycle detection, topological sorting, SCCs, bridges and articulation points. BFS’s level structure is what makes it the right tool for distances. Choose by which property you need.

3. Grids as graphs

An R x C grid is a graph with R·C vertices and 4 (or 8) edges per vertex. Almost every “islands”, “maze”, “flood fill” or “spreading” problem is BFS/DFS with the adjacency computed rather than stored.

DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS8 = DIRS4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))

def num_islands(grid):
    """Grid DFS with in-place marking: no separate visited set. Mutates the input."""
    if not grid: return 0
    R, C = len(grid), len(grid[0]); count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != '1': continue
            count += 1
            st = [(r, c)]                                     # iterative: a 1e6-cell grid is fine
            while st:
                i, j = st.pop()
                if not (0 <= i < R and 0 <= j < C) or grid[i][j] != '1': continue
                grid[i][j] = '0'                              # sink it
                st.extend([(i+1, j), (i-1, j), (i, j+1), (i, j-1)])
    return count

def rotting_oranges(grid):
    """MULTI-SOURCE BFS: seed the queue with every source, then expand by levels."""
    R, C = len(grid), len(grid[0])
    q = deque((r, c) for r in range(R) for c in range(C) if grid[r][c] == 2)
    fresh = sum(grid[r][c] == 1 for r in range(R) for c in range(C))
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):                               # process exactly one level
            r, c = q.popleft()
            for dr, dc in DIRS4:
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes

Multi-source BFS is the technique to have in your pocket: seeding the queue with all sources at distance 0 computes, in one pass, the distance from every cell to its nearest source. It solves rotting oranges, “01 matrix” (distance to nearest zero), “walls and gates”, and “shortest bridge” — each of which looks like it needs one BFS per source (O(V^2)) and actually needs one BFS total (O(V)).

0-1 BFS

When edge weights are only 0 or 1, a deque replaces the heap and Dijkstra’s log factor disappears.

def zero_one_bfs(grid):
    """Minimum obstacle removals to cross a grid. Weight-0 edges go to the FRONT, weight-1 to the back."""
    R, C = len(grid), len(grid[0])
    dist = [[math.inf] * C for _ in range(R)]
    dist[0][0] = grid[0][0]
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < R and 0 <= nc < C): continue
            w = grid[nr][nc]
            if dist[r][c] + w < dist[nr][nc]:
                dist[nr][nc] = dist[r][c] + w
                (dq.appendleft if w == 0 else dq.append)((nr, nc))
    return dist[R-1][C-1]

The invariant is that the deque holds at most two distinct distance values, so front-insertion keeps it sorted — exactly what the heap was buying you. O(V + E) instead of O(E log V).

4. Topological sort

Signal: “order the tasks”, “course prerequisites”, “build order”, “can this be scheduled”, “alien dictionary”. Requires a DAG; the absence of a valid order is the cycle detector.

Kahn’s algorithm (BFS on in-degrees)

def topo_kahn(n, edges):
    adj = defaultdict(list); indeg = [0] * n
    for u, v in edges: adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)     # everything with no prerequisites
    order = []
    while q:
        v = q.popleft(); order.append(v)
        for nx in adj[v]:
            indeg[nx] -= 1
            if indeg[nx] == 0: q.append(nx)             # its last prerequisite just finished
    return order if len(order) == n else None           # short order -> a cycle exists

DFS post-order

def topo_dfs(n, edges):
    adj = defaultdict(list)
    for u, v in edges: adj[u].append(v)
    WHITE, GRAY, BLACK = 0, 1, 2                        # unvisited / on the stack / done
    color = [WHITE] * n; order = []
    def go(v):
        color[v] = GRAY
        for nx in adj[v]:
            if color[nx] == GRAY: return False          # BACK EDGE -> cycle
            if color[nx] == WHITE and not go(nx): return False
        color[v] = BLACK
        order.append(v)                                 # post-order
        return True
    for v in range(n):
        if color[v] == WHITE and not go(v): return None
    return order[::-1]                                  # reverse post-order IS a topological order

Verified: both produce valid topological orders on the same DAG (checked by asserting every edge goes forward), and both return None on a 2-cycle.

Once you have a topological order, DAG shortest and longest paths become one linear relaxation pass — which is why “longest path in a DAG” is easy and “longest path in a general graph” is NP-hard. That contrast is a good thing to volunteer.

Three-colour DFS is the general directed-cycle detector. The GRAY set is the current recursion stack; a back edge to a GRAY vertex is a cycle. A BLACK neighbour is fine — it is a forward or cross edge to a finished subtree. Using a single visited set instead of three colours is the classic wrong answer, because it reports cross edges as cycles.

5. Cycle detection

def has_cycle_undirected(n, edges):
    """DSU. Also the core of Kruskal: an edge joining two vertices already in one component is a cycle."""
    parent = list(range(n))
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv: return True
        parent[rv] = ru
    return False

For undirected DFS the subtlety is that the edge you came in on is not a cycle: you must skip the parent (and, with multi-edges, skip only one occurrence of it).

6. Shortest paths

Dijkstra

def dijkstra(adj, s):
    """Non-negative weights only. Lazy deletion: push duplicates, skip stale pops."""
    dist = {s: 0}; pq = [(0, s)]
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist.get(v, math.inf): continue          # stale entry — this is the lazy-deletion check
        for n, w in adj[v].items():
            nd = d + w
            if nd < dist.get(n, math.inf):
                dist[n] = nd
                heapq.heappush(pq, (nd, n))
    return dist

def dijkstra_path(adj, s, t):
    """Same, plus a predecessor map to reconstruct the path, and early exit at t."""
    dist = {s: 0}; prev = {}; pq = [(0, s)]
    while pq:
        d, v = heapq.heappop(pq)
        if v == t: break                                 # safe: v is finalized when popped
        if d > dist.get(v, math.inf): continue
        for n, w in adj[v].items():
            nd = d + w
            if nd < dist.get(n, math.inf):
                dist[n] = nd; prev[n] = v; heapq.heappush(pq, (nd, n))
    if t not in dist: return None
    path = [t]
    while path[-1] != s: path.append(prev[path[-1]])
    return dist[t], path[::-1]

Verified: dijkstra on the test graph gives {'a':0, 'c':1, 'b':3, 'd':8} and dijkstra_path(a, d) returns (8, ['a','c','b','d']) — note the optimal path goes through c and b rather than taking the direct a-d edge of weight 8 via c-d.

Why non-negative weights are required. Dijkstra finalizes a vertex the moment it is popped, on the grounds that no future path can be shorter. A negative edge breaks that: a longer-so-far path could later drop below. The failure is silent — you get a wrong answer, not an error — which is exactly what makes it a good interview question.

Lazy deletion vs decrease-key. The version above pushes a new entry every time it improves a distance and skips stale pops. That is O(E log E) with up to E heap entries. The alternative is an indexed heap with decrease_key (see Python data structures §16), giving O(E log V) with at most V entries. For sparse graphs log E and log V differ by a constant, and lazy deletion is ten lines shorter — so lazy is the right interview answer, and knowing both is the right interview answer to the follow-up.

Bellman-Ford

def bellman_ford(n, edges, s):
    """Handles negative weights. V-1 relaxation passes, then one more to detect negative cycles."""
    dist = [math.inf] * n; dist[s] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]: dist[v] = dist[u] + w; changed = True
        if not changed: break                            # early exit: already converged
    for u, v, w in edges:
        if dist[u] + w < dist[v]: return None            # still improving -> negative cycle
    return dist

Verified: correct distances with a negative edge ([0, -1, 1, 4]), and None on a graph with a negative cycle.

Why V-1 passes: a shortest path visits at most V vertices, hence at most V-1 edges, and each pass guarantees all shortest paths of one more edge are found. If a Vth pass still improves something, there is no shortest path — you can loop a negative cycle forever.

This is the algorithm behind currency arbitrage detection: take -log(rate) as the weight, and a negative cycle is a profitable loop. Mentioning that application lands well.

Floyd-Warshall

def floyd_warshall(n, edges):
    """All pairs, O(V^3). k is the OUTER loop — that is the whole algorithm."""
    d = [[math.inf] * n for _ in range(n)]
    for i in range(n): d[i][i] = 0
    for u, v, w in edges: d[u][v] = min(d[u][v], w)
    for k in range(n):                                   # k = "intermediate vertices allowed so far"
        for i in range(n):
            if d[i][k] == math.inf: continue             # cheap pruning
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]: d[i][j] = d[i][k] + d[k][j]
    return d

The DP formulation: d[k][i][j] = shortest i->j path using only vertices < k as intermediates. The k loop must be outermost; swapping the loops is the classic bug and produces wrong answers on some inputs but not others, which makes it painful to debug. d[i][i] < 0 after the run means a negative cycle through i.

Also useful for transitive closure (replace min/plus with or/and) and for detecting whether any path exists between all pairs.

A*

def astar(grid, start, goal):
    """Dijkstra plus a heuristic. Admissible h (never overestimates) -> optimal."""
    R, C = len(grid), len(grid[0])
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])     # Manhattan, admissible for 4-way moves
    g = {start: 0}
    pq = [(h(start), 0, start)]
    while pq:
        _, gc, v = heapq.heappop(pq)
        if v == goal: return gc
        if gc > g.get(v, math.inf): continue
        for dr, dc in DIRS4:
            n = (v[0] + dr, v[1] + dc)
            if not (0 <= n[0] < R and 0 <= n[1] < C) or grid[n[0]][n[1]] == 1: continue
            ng = gc + 1
            if ng < g.get(n, math.inf):
                g[n] = ng
                heapq.heappush(pq, (ng + h(n), ng, n))
    return -1

A* orders the frontier by g + h instead of g. Admissible (h never overestimates the true remaining cost) guarantees optimality; consistent/monotone (h(u) <= w(u,v) + h(v)) additionally guarantees you never need to re-expand a node. With h = 0 it degenerates to Dijkstra; with h too large it becomes greedy best-first and loses optimality. Manhattan distance is admissible for 4-directional grids; Euclidean is admissible for 8-directional; using Manhattan for 8-directional movement is inadmissible and a nice trap.

Shortest-path summary

7. Minimum spanning trees

A spanning tree with minimum total edge weight. Both classic algorithms are greedy, and both are justified by the cut property: for any partition of the vertices, the lightest edge crossing the cut is in some MST.

def kruskal(n, edges):
    """Sort all edges, add each if it joins two different components. Needs DSU."""
    parent = list(range(n)); size = [1] * n
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    total = 0; used = []
    for w, u, v in sorted(edges):                  # edges as (weight, u, v) so sorting is free
        ru, rv = find(u), find(v)
        if ru == rv: continue                      # would create a cycle
        if size[ru] < size[rv]: ru, rv = rv, ru
        parent[rv] = ru; size[ru] += size[rv]
        total += w; used.append((u, v, w))
    return total, used

def prim(n, adj):
    """Grow one tree from a seed, always taking the lightest edge leaving it. Needs a heap."""
    seen = [False] * n; pq = [(0, 0)]; total = 0; count = 0
    while pq and count < n:
        w, v = heapq.heappop(pq)
        if seen[v]: continue                       # lazy deletion again
        seen[v] = True; total += w; count += 1
        for nx, ww in adj[v].items():
            if not seen[nx]: heapq.heappush(pq, (ww, nx))
    return total if count == n else None           # None -> the graph is disconnected

Verified: both return 7 on the same graph.

Related facts worth having: an MST is unique if all edge weights are distinct; an MST also minimizes the maximum edge on the path between any two vertices (the minimax path property, which is why MSTs solve “minimize the worst hop”); and “maximum spanning tree” is the same algorithm with the comparison flipped.

8. Strongly connected components

An SCC is a maximal set of vertices that are all mutually reachable. Contracting each SCC to a single node yields the condensation, which is always a DAG — the standard way to make a cyclic dependency graph topologically sortable.

def tarjan_scc(n, adj):
    """One DFS pass. low[v] = smallest index reachable from v's subtree via at most one back edge."""
    index = [None] * n; low = [0] * n; on = [False] * n
    st = []; counter = [0]; res = []
    def go(v):
        index[v] = low[v] = counter[0]; counter[0] += 1
        st.append(v); on[v] = True
        for w in adj[v]:
            if index[w] is None:
                go(w); low[v] = min(low[v], low[w])          # tree edge
            elif on[w]:
                low[v] = min(low[v], index[w])               # back edge to a vertex still on the stack
        if low[v] == index[v]:                               # v is the ROOT of an SCC
            comp = []
            while True:
                w = st.pop(); on[w] = False; comp.append(w)
                if w == v: break
            res.append(sorted(comp))
    for v in range(n):
        if index[v] is None: go(v)
    return sorted(res)

def kosaraju(n, adj):
    """Two passes: DFS post-order on G, then DFS on the reverse graph in reverse post-order."""
    order = []; seen = [False] * n
    def go1(v):
        seen[v] = True
        for w in adj[v]:
            if not seen[w]: go1(w)
        order.append(v)
    for v in range(n):
        if not seen[v]: go1(v)
    radj = defaultdict(list)
    for v in range(n):
        for w in adj[v]: radj[w].append(v)
    comp = [None] * n; res = []
    def go2(v, c):
        comp[v] = c; cur.append(v)
        for w in radj[v]:
            if comp[w] is None: go2(w, c)
    c = 0
    for v in reversed(order):
        if comp[v] is None:
            cur = []; go2(v, c); res.append(sorted(cur)); c += 1
    return sorted(res)

Verified: both find [[0,1,2],[3,4,5]] on the same graph.

Tarjan does one pass and is what you would use in production; Kosaraju needs two passes and the reverse graph but is much easier to explain and to get right under pressure. The same low-link machinery finds bridges (low[w] > index[v] for a tree edge v-w) and articulation points (low[w] >= index[v], with a special case for the root).

Applications: 2-SAT (build the implication graph; satisfiable iff no variable shares an SCC with its negation), deadlock detection, finding cyclic module dependencies, and condensing a cyclic graph so you can topologically sort it.

9. Bipartite graphs, colouring, and matching

def is_bipartite(n, adj):
    """2-colour with BFS. A conflict means an odd cycle, which means not bipartite."""
    color = [0] * n                                   # 0 = uncoloured, 1 / -1 = the two sides
    for s in range(n):
        if color[s]: continue                         # a new component
        color[s] = 1; q = deque([s])
        while q:
            v = q.popleft()
            for w in adj[v]:
                if color[w] == color[v]: return False
                if not color[w]: color[w] = -color[v]; q.append(w)
    return True

Verified: the 4-cycle is bipartite, the triangle is not. Bipartite iff no odd-length cycle — that equivalence is the fact to state.

The looping over all s matters: a graph can be disconnected, and a single BFS only colours one component. Forgetting it is the standard bug.

Uses: “possible bipartition” / “divide into two teams”, conflict graphs, and as the precondition for matching problems. Beyond 2 colours, graph colouring is NP-hard (3-colourability already is), which is worth saying if asked to generalize.

Maximum bipartite matching is Hopcroft-Karp in O(E·sqrt(V)); the simpler Kuhn’s algorithm (augmenting paths via DFS) is O(V·E) and much easier to write. Konig’s theorem (max matching = min vertex cover in a bipartite graph) is the bridge to min-cut problems, and Hall’s theorem gives the condition for a perfect matching.

10. Trees: the core operations

A tree is a graph with no cycles, so all the graph algorithms apply — but the structure makes them simpler: no visited set is needed for a rooted tree traversal (just do not go back to the parent), and there is exactly one path between any two nodes.

class TN:
    __slots__ = ("v", "l", "r")
    def __init__(self, v, l=None, r=None): self.v = v; self.l = l; self.r = r

def level_order(root):
    """BFS with an explicit level loop — the pattern behind every 'per level' question."""
    if not root: return []
    res = []; q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):                   # snapshot the level size BEFORE appending children
            n = q.popleft(); level.append(n.v)
            if n.l: q.append(n.l)
            if n.r: q.append(n.r)
        res.append(level)
    return res

def max_depth(root):
    return 0 if not root else 1 + max(max_depth(root.l), max_depth(root.r))

def is_balanced(root):
    """Height-balanced check in ONE pass: return -1 as a sentinel for 'already unbalanced'."""
    def h(n):
        if not n: return 0
        lh = h(n.l)
        if lh < 0: return -1
        rh = h(n.r)
        if rh < 0 or abs(lh - rh) > 1: return -1
        return 1 + max(lh, rh)
    return h(root) >= 0

def diameter(root):
    """Longest path between any two nodes, in edges. The path may not pass through the root."""
    best = [0]
    def h(n):
        if not n: return 0
        lh, rh = h(n.l), h(n.r)
        best[0] = max(best[0], lh + rh)           # the path THROUGH n
        return 1 + max(lh, rh)                    # the height returned UPWARD
    h(root)
    return best[0]

def lca(root, p, q):
    """Lowest common ancestor in a general binary tree. O(n), one pass."""
    if not root or root.v in (p, q): return root
    l, r = lca(root.l, p, q), lca(root.r, p, q)
    return root if l and r else (l or r)          # found on both sides -> this is the LCA

def lca_bst(root, p, q):
    """In a BST it is O(h) and iterative: walk down until p and q diverge."""
    while root:
        if p < root.v and q < root.v: root = root.l
        elif p > root.v and q > root.v: root = root.r
        else: return root
    return None

def path_sum_count(root, target):
    """Count downward paths summing to target. Prefix sums on a tree path — note the undo."""
    prefix = defaultdict(int); prefix[0] = 1
    def go(n, run):
        if not n: return 0
        run += n.v
        cnt = prefix[run - target]
        prefix[run] += 1
        cnt += go(n.l, run) + go(n.r, run)
        prefix[run] -= 1                          # BACKTRACK: this prefix is not on sibling paths
        return cnt
    return go(root, 0)

def serialize(root):
    """Pre-order with explicit null markers. This is what makes it uniquely decodable."""
    res = []
    def go(n):
        if not n: res.append('#'); return
        res.append(str(n.v)); go(n.l); go(n.r)
    go(root)
    return ','.join(res)

def deserialize(s):
    it = iter(s.split(','))
    def go():
        v = next(it)
        if v == '#': return None
        n = TN(int(v)); n.l = go(); n.r = go(); return n
    return go()

def right_side_view(root):
    if not root: return []
    res = []; q = deque([root])
    while q:
        res.append(q[-1].v)                       # last node of the level
        for _ in range(len(q)):
            n = q.popleft()
            if n.l: q.append(n.l)
            if n.r: q.append(n.r)
    return res

Verified: on the complete tree [1..7], level order is [[1],[2,3],[4,5,6,7]], depth 3, balanced, diameter 4, lca(4,5) == 2, lca(4,7) == 1, right view [1,3,7], and deserialize(serialize(t)) round-trips. On the BST [8,4,12,2,6,10,14], lca_bst(2,6) == 4 and lca_bst(2,14) == 8. path_sum_count finds the 2 valid paths in the test tree.

Serialization is the interesting one

Pre-order with null markers is uniquely decodable, which is why the '#' matters. Without markers, pre-order alone is ambiguous. Two related facts that come up as follow-ups:

• Pre-order + in-order determines a binary tree uniquely (as does post-order + in-order).
• Pre-order + post-order does not, in general — but it does for a full binary tree.
• For a BST, pre-order alone is sufficient, because the in-order is just the sorted values.

11. Tree techniques worth naming

Return more than you need from the recursion. is_balanced returns a height and signals failure with -1; diameter returns a height while accumulating a best-so-far. Bundling extra information into the return value (or a small tuple/dataclass) is what turns an O(n^2) “recompute the height at every node” solution into O(n). This is the single most transferable tree technique.

Post-order for bottom-up, pre-order for top-down. “Validate a BST” and “sum from root” are top-down (pass constraints/accumulators down); “height”, “diameter”, “count nodes matching a subtree property” are bottom-up (compute from children). Choosing wrong makes the problem much harder.

Backtracking state on tree paths. path_sum_count maintains a prefix-sum map and decrements on the way out, because a prefix on the left branch is not on the right branch. The same undo pattern appears in “path sum II”, “binary tree paths”, and anything asking about root-to-leaf paths.

Morris traversal gives O(1)-space in-order by temporarily threading right pointers — see TypeScript §14.

Euler tour / flattening. Recording entry and exit times during a DFS turns subtree queries into range queries on an array, which a segment tree or Fenwick tree then answers in O(log n). This is the bridge from tree problems to the range-query structures.

Binary lifting for LCA. Precompute up[k][v] = the 2^k-th ancestor of v in O(n log n), then answer each LCA query in O(log n) by lifting both nodes to the same depth and then jumping together. The alternative is an Euler tour plus a sparse table for O(1) queries after O(n log n) preprocessing.

Small-to-large merging and DSU on tree are the standard ways to answer “for every subtree, something about the multiset of values in it” in O(n log n) rather than O(n^2).

Tree DP — rerooting, “maximum path sum”, “house robber III”, tree diameter, and independent-set on a tree — is in Dynamic programming.

12. Test run

  ok  BFS (order + levels), DFS recursive and iterative agree
  ok  components, islands (grid DFS), rotting oranges (multi-source BFS by levels)
  ok  0-1 BFS with a deque: O(V+E) instead of Dijkstra's O(E log V)
  ok  topological sort: Kahn (indegree BFS) and DFS post-order; both detect cycles
  ok  cycle detection: DSU for undirected, three-colour DFS for directed
  ok  shortest paths: Dijkstra (+path), Bellman-Ford (+negative cycle), Floyd-Warshall, A*
  ok  MST: Kruskal (sort + DSU) and Prim (heap) agree on total weight
  ok  SCC: Tarjan (one pass, low-link) and Kosaraju (two passes) agree
  ok  bipartite check via 2-colouring BFS
  ok  trees: level order, depth, balanced, diameter, LCA (general + BST), path-sum-III,
      serialize/deserialize, right view

ALL GRAPH/TREE ASSERTIONS PASSED (10 groups)

13. Interview questions

Q: BFS or DFS?

A: BFS when you need the shortest number of steps, or any level structure. DFS when you need connectivity, cycles, topological order, or recursive subtree computation. BFS costs O(width) memory, DFS costs O(depth).

Q: Why not use Dijkstra for an unweighted graph?

A: BFS already gives the optimal answer in O(V+E). Dijkstra adds a heap for no benefit — with equal weights it is BFS with a log factor bolted on.

Q: Why does Dijkstra fail with negative weights?

A: It finalizes a vertex when popped, assuming no later path can beat it. A negative edge can make a longer-so-far path become shorter, so the assumption breaks and you get a silently wrong answer. Use Bellman-Ford, or reweight with Johnson’s algorithm.

Q: Explain the stale-entry check in Dijkstra.

A: With lazy deletion you push a new heap entry every time you improve a distance, so old entries remain. if d > dist[v]: continue skips them. Without it you would relax a vertex’s neighbours multiple times — still correct, but wasteful.

Q: How do you detect a negative cycle?

A: Run Bellman-Ford for V-1 passes, then do one more. If anything still relaxes, a negative cycle is reachable. To find which cycle, follow predecessor pointers from the relaxed vertex.

Q: How do you find shortest paths in a DAG with negative weights?

A: Topological order, then one relaxation pass in that order. O(V+E), and it works for longest paths too — unlike general graphs, where longest path is NP-hard.

Q: Kruskal or Prim?

A: Kruskal for sparse graphs and when edges are already sorted, and it handles disconnected graphs by producing a forest. Prim for dense graphs and adjacency-matrix input. Both O(E log V)-ish.

Q: Is the MST unique?

A: If all edge weights are distinct, yes. With ties there can be several, though they all have the same total weight. An MST also minimizes the maximum edge on any path between two vertices.

Q: How would you tell whether a directed graph has a cycle?

A: Three-colour DFS: a back edge to a GRAY (on-stack) vertex is a cycle. Or Kahn’s algorithm — if it emits fewer than V vertices, a cycle exists. A single visited set is the wrong answer; it misclassifies cross edges.

Q: How do you find the number of connected components?

A: Loop over vertices; for each unvisited one, run a BFS/DFS and increment a counter. Or union-find and count distinct roots — better when edges arrive incrementally.

Q: What is a strongly connected component and where does it matter?

A: A maximal mutually-reachable set in a directed graph. Contracting SCCs gives a DAG, which is how you topologically order a graph with cycles. It is also the core of 2-SAT and of deadlock and circular-dependency detection.

Q: How do you check whether a graph is bipartite?

A: 2-colour with BFS across all components; a conflict means an odd cycle. Bipartite is exactly “no odd-length cycle”.

Q: How do you handle a grid problem with 1e6 cells?

A: Iterative BFS/DFS (recursion would overflow), an in-place visited marker instead of a set, and direction vectors. If it is unweighted shortest path, BFS; if weights are 0/1, a deque; if weights are arbitrary, Dijkstra with the heap keyed on cost.

Q: What is multi-source BFS and when does it help?

A: Seed the queue with every source at distance 0. One O(V) pass then gives every cell its distance to the nearest source, instead of running one BFS per source at O(V^2). Solves rotting oranges, 01 matrix, walls and gates.

Q: How do you find the diameter of a tree?

A: For a binary tree, one post-order pass returning heights while tracking left + right at each node. For a general tree, two BFS runs: the farthest node from any start, then the farthest from that — that distance is the diameter.

Q: LCA in a binary tree versus a BST?

A: General tree: recurse; if both subtrees return something, the current node is the LCA — O(n). BST: walk down while both targets are on the same side — O(h), iterative, no recursion. With many queries on a static tree, precompute with binary lifting for O(log n) each.

Q: How do you serialize a binary tree?

A: Pre-order with explicit null markers, which makes it uniquely decodable. Level-order with markers also works. Note that pre-order + in-order determines the tree, pre-order + post-order does not (except for full binary trees), and for a BST pre-order alone suffices.

Q: Validate a BST.

A: In-order traversal must be strictly increasing, or recurse carrying (lo, hi) bounds. Comparing each node only to its children is the classic wrong answer.

Q: How do you avoid recomputing heights in tree problems?

A: Return the height and the answer-so-far from one recursion, using a sentinel or a tuple. That is what turns O(n^2) into O(n), and it generalizes to almost every “bottom-up tree property” question.

Q: How would you detect a cycle in a very large graph that does not fit in memory?

A: Externalize: process edges in sorted order with an on-disk union-find for the undirected case, or partition the graph and use a distributed framework (Pregel/GraphX-style vertex-centric iteration). Also worth mentioning: for a stream of edges, union-find is online and needs only O(V) state.

Q: What is the difference between a bridge and an articulation point?

A: A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex. Both come from the same Tarjan low-link DFS: bridge when low[child] > disc[v], articulation point when low[child] >= disc[v] (with a special case for the DFS root).

Q: When would you use A* over Dijkstra?

A: Single source and single target, with a cheap admissible heuristic — pathfinding on a map or a game grid. It explores far fewer nodes. With h = 0 it is Dijkstra; with an inadmissible h it is fast but no longer optimal.

Q: How do you find the shortest path when edges have weights 0 and 1 only?

A: 0-1 BFS: a deque where weight-0 edges push to the front and weight-1 to the back. O(V+E), no heap.

Q: Word ladder / minimum transformations — how do you model it?

A: Vertices are words, edges connect words at Hamming distance 1, and the answer is BFS. The practical trick is building adjacency lazily via wildcard buckets (h*t -> {hat, hit, hot}) so you avoid comparing every pair, and bidirectional BFS if the graph is wide.

Next: Dynamic programming.

Verify it yourself

graph/g.py

from collections import defaultdict, deque
import heapq, math
out=[]
def ok(m): out.append("  ok  "+m)

# ---------- traversals ----------
def bfs(adj, s):
    seen={s}; q=deque([s]); order=[]
    while q:
        v=q.popleft(); order.append(v)
        for n in adj[v]:
            if n not in seen: seen.add(n); q.append(n)
    return order
def bfs_levels(adj, s):
    seen={s}; q=deque([s]); dist={s:0}
    while q:
        v=q.popleft()
        for n in adj[v]:
            if n not in seen: seen.add(n); dist[n]=dist[v]+1; q.append(n)
    return dist
def dfs_rec(adj, s, seen=None, order=None):
    if seen is None: seen, order = set(), []
    seen.add(s); order.append(s)
    for n in adj[s]:
        if n not in seen: dfs_rec(adj, n, seen, order)
    return order
def dfs_iter(adj, s):
    seen=set(); st=[s]; order=[]
    while st:
        v=st.pop()
        if v in seen: continue
        seen.add(v); order.append(v)
        for n in reversed(adj[v]):
            if n not in seen: st.append(n)
    return order
adj = defaultdict(list, {1:[2,3],2:[4],3:[4],4:[5],5:[]})
assert bfs(adj,1)==[1,2,3,4,5]
assert bfs_levels(adj,1)=={1:0,2:1,3:1,4:2,5:3}
assert dfs_rec(adj,1)==[1,2,4,5,3]
assert dfs_iter(adj,1)==[1,2,4,5,3]
ok("BFS (order + levels), DFS recursive and iterative agree")

# ---------- connected components / grid ----------
def count_components(n, edges):
    adj=defaultdict(list)
    for u,v in edges: adj[u].append(v); adj[v].append(u)
    seen=set(); c=0
    for s in range(n):
        if s in seen: continue
        c+=1; st=[s]
        while st:
            v=st.pop()
            if v in seen: continue
            seen.add(v)
            st.extend(x for x in adj[v] if x not in seen)
    return c
def num_islands(grid):
    if not grid: return 0
    R,C=len(grid),len(grid[0]); count=0
    for r in range(R):
        for c in range(C):
            if grid[r][c]!='1': continue
            count+=1; st=[(r,c)]
            while st:
                i,j=st.pop()
                if not (0<=i<R and 0<=j<C) or grid[i][j]!='1': continue
                grid[i][j]='0'
                st.extend([(i+1,j),(i-1,j),(i,j+1),(i,j-1)])
    return count
def rotting_oranges(grid):
    R,C=len(grid),len(grid[0])
    q=deque((r,c) for r in range(R) for c in range(C) if grid[r][c]==2)   # MULTI-SOURCE BFS
    fresh=sum(grid[r][c]==1 for r in range(R) for c in range(C))
    minutes=0
    while q and fresh:
        for _ in range(len(q)):
            r,c=q.popleft()
            for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr,nc=r+dr,c+dc
                if 0<=nr<R and 0<=nc<C and grid[nr][nc]==1:
                    grid[nr][nc]=2; fresh-=1; q.append((nr,nc))
        minutes+=1
    return -1 if fresh else minutes
assert count_components(5,[(0,1),(1,2),(3,4)])==2
assert num_islands([list("11000"),list("11000"),list("00100"),list("00011")])==3
assert rotting_oranges([[2,1,1],[1,1,0],[0,1,1]])==4
assert rotting_oranges([[2,1,1],[0,1,1],[1,0,1]])==-1
ok("components, islands (grid DFS), rotting oranges (multi-source BFS by levels)")

# ---------- 0-1 BFS ----------
def zero_one_bfs(grid):
    """Minimum obstacle removals: edges cost 0 or 1 -> deque instead of a heap."""
    R,C=len(grid),len(grid[0])
    dist=[[math.inf]*C for _ in range(R)]; dist[0][0]=grid[0][0]
    dq=deque([(0,0)])
    while dq:
        r,c=dq.popleft()
        for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr,nc=r+dr,c+dc
            if not (0<=nr<R and 0<=nc<C): continue
            w=grid[nr][nc]
            if dist[r][c]+w < dist[nr][nc]:
                dist[nr][nc]=dist[r][c]+w
                (dq.appendleft if w==0 else dq.append)((nr,nc))
    return dist[R-1][C-1]
assert zero_one_bfs([[0,1,1],[1,1,0],[1,1,0]])==2
ok("0-1 BFS with a deque: O(V+E) instead of Dijkstra's O(E log V)")

# ---------- topological sort ----------
def topo_kahn(n, edges):
    adj=defaultdict(list); indeg=[0]*n
    for u,v in edges: adj[u].append(v); indeg[v]+=1
    q=deque(i for i in range(n) if indeg[i]==0); order=[]
    while q:
        v=q.popleft(); order.append(v)
        for nx in adj[v]:
            indeg[nx]-=1
            if indeg[nx]==0: q.append(nx)
    return order if len(order)==n else None       # None means a cycle exists
def topo_dfs(n, edges):
    adj=defaultdict(list)
    for u,v in edges: adj[u].append(v)
    WHITE,GRAY,BLACK=0,1,2
    color=[WHITE]*n; order=[]
    def go(v):
        color[v]=GRAY
        for nx in adj[v]:
            if color[nx]==GRAY: return False      # back edge -> cycle
            if color[nx]==WHITE and not go(nx): return False
        color[v]=BLACK; order.append(v); return True
    for v in range(n):
        if color[v]==WHITE and not go(v): return None
    return order[::-1]
e=[(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]
t1, t2 = topo_kahn(6,e), topo_dfs(6,e)
def valid_topo(order, n, edges):
    pos={v:i for i,v in enumerate(order)}
    return len(order)==n and all(pos[u]<pos[v] for u,v in edges)
assert valid_topo(t1,6,e) and valid_topo(t2,6,e)
assert topo_kahn(2,[(0,1),(1,0)]) is None and topo_dfs(2,[(0,1),(1,0)]) is None
ok("topological sort: Kahn (indegree BFS) and DFS post-order; both detect cycles")

# ---------- cycle detection ----------
def has_cycle_undirected(n, edges):
    parent=list(range(n))
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    for u,v in edges:
        ru,rv=find(u),find(v)
        if ru==rv: return True
        parent[rv]=ru
    return False
assert has_cycle_undirected(3,[(0,1),(1,2),(2,0)])
assert not has_cycle_undirected(3,[(0,1),(1,2)])
ok("cycle detection: DSU for undirected, three-colour DFS for directed")

# ---------- shortest paths ----------
def dijkstra(adj, s):
    dist={s:0}; pq=[(0,s)]
    while pq:
        d,v=heapq.heappop(pq)
        if d>dist.get(v,math.inf): continue        # stale entry (lazy deletion)
        for n,w in adj[v].items():
            nd=d+w
            if nd<dist.get(n,math.inf):
                dist[n]=nd; heapq.heappush(pq,(nd,n))
    return dist
def dijkstra_path(adj, s, t):
    dist={s:0}; prev={}; pq=[(0,s)]
    while pq:
        d,v=heapq.heappop(pq)
        if v==t: break
        if d>dist.get(v,math.inf): continue
        for n,w in adj[v].items():
            nd=d+w
            if nd<dist.get(n,math.inf): dist[n]=nd; prev[n]=v; heapq.heappush(pq,(nd,n))
    if t not in dist: return None
    path=[t]
    while path[-1]!=s: path.append(prev[path[-1]])
    return dist[t], path[::-1]
def bellman_ford(n, edges, s):
    dist=[math.inf]*n; dist[s]=0
    for _ in range(n-1):
        changed=False
        for u,v,w in edges:
            if dist[u]+w < dist[v]: dist[v]=dist[u]+w; changed=True
        if not changed: break
    for u,v,w in edges:
        if dist[u]+w < dist[v]: return None          # negative cycle
    return dist
def floyd_warshall(n, edges):
    d=[[math.inf]*n for _ in range(n)]
    for i in range(n): d[i][i]=0
    for u,v,w in edges: d[u][v]=min(d[u][v],w)
    for k in range(n):
        for i in range(n):
            if d[i][k]==math.inf: continue
            for j in range(n):
                if d[i][k]+d[k][j] < d[i][j]: d[i][j]=d[i][k]+d[k][j]
    return d
def astar(grid, start, goal):
    R,C=len(grid),len(grid[0])
    h=lambda p: abs(p[0]-goal[0])+abs(p[1]-goal[1])   # Manhattan: admissible and consistent here
    g={start:0}; pq=[(h(start),0,start)]
    while pq:
        _,gc,v=heapq.heappop(pq)
        if v==goal: return gc
        if gc>g.get(v,math.inf): continue
        for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
            n=(v[0]+dr,v[1]+dc)
            if not (0<=n[0]<R and 0<=n[1]<C) or grid[n[0]][n[1]]==1: continue
            ng=gc+1
            if ng<g.get(n,math.inf): g[n]=ng; heapq.heappush(pq,(ng+h(n),ng,n))
    return -1
wadj=defaultdict(dict)
for u,v,w in [('a','b',4),('a','c',1),('c','b',2),('b','d',5),('c','d',8)]:
    wadj[u][v]=w
assert dijkstra(wadj,'a')=={'a':0,'c':1,'b':3,'d':8}
assert dijkstra_path(wadj,'a','d')==(8,['a','c','b','d'])
edges3=[(0,1,4),(0,2,1),(2,1,-2),(1,3,5)]
assert bellman_ford(4,edges3,0)==[0,-1,1,4]
assert bellman_ford(3,[(0,1,1),(1,2,-3),(2,0,1)],0) is None
fw=floyd_warshall(4,[(0,1,4),(0,2,1),(2,1,2),(1,3,5)])
assert fw[0][3]==8 and fw[0][1]==3
assert astar([[0,0,0],[1,1,0],[0,0,0]],(0,0),(2,2))==4
ok("shortest paths: Dijkstra (+path), Bellman-Ford (+negative cycle), Floyd-Warshall, A*")

# ---------- MST ----------
def kruskal(n, edges):
    parent=list(range(n)); size=[1]*n
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    total=0; used=[]
    for w,u,v in sorted(edges):
        ru,rv=find(u),find(v)
        if ru==rv: continue
        if size[ru]<size[rv]: ru,rv=rv,ru
        parent[rv]=ru; size[ru]+=size[rv]
        total+=w; used.append((u,v,w))
    return total, used
def prim(n, adj):
    seen=[False]*n; pq=[(0,0)]; total=0; count=0
    while pq and count<n:
        w,v=heapq.heappop(pq)
        if seen[v]: continue
        seen[v]=True; total+=w; count+=1
        for nx,ww in adj[v].items():
            if not seen[nx]: heapq.heappush(pq,(ww,nx))
    return total if count==n else None
E=[(1,0,1),(2,1,2),(3,0,2),(4,2,3),(5,1,3)]
tot,used=kruskal(4,E)
padj=defaultdict(dict)
for w,u,v in E: padj[u][v]=w; padj[v][u]=w
assert tot==7 and prim(4,padj)==7
ok("MST: Kruskal (sort + DSU) and Prim (heap) agree on total weight")

# ---------- SCC ----------
def tarjan_scc(n, adj):
    index=[None]*n; low=[0]*n; on=[False]*n; st=[]; counter=[0]; res=[]
    def go(v):
        index[v]=low[v]=counter[0]; counter[0]+=1
        st.append(v); on[v]=True
        for w in adj[v]:
            if index[w] is None: go(w); low[v]=min(low[v],low[w])
            elif on[w]: low[v]=min(low[v],index[w])
        if low[v]==index[v]:
            comp=[]
            while True:
                w=st.pop(); on[w]=False; comp.append(w)
                if w==v: break
            res.append(sorted(comp))
    for v in range(n):
        if index[v] is None: go(v)
    return sorted(res)
def kosaraju(n, adj):
    order=[]; seen=[False]*n
    def go1(v):
        seen[v]=True
        for w in adj[v]:
            if not seen[w]: go1(w)
        order.append(v)
    for v in range(n):
        if not seen[v]: go1(v)
    radj=defaultdict(list)
    for v in range(n):
        for w in adj[v]: radj[w].append(v)
    comp=[None]*n; res=[]
    def go2(v, c):
        comp[v]=c; cur.append(v)
        for w in radj[v]:
            if comp[w] is None: go2(w,c)
    c=0
    for v in reversed(order):
        if comp[v] is None:
            cur=[]; go2(v,c); res.append(sorted(cur)); c+=1
    return sorted(res)
sadj=defaultdict(list,{0:[1],1:[2],2:[0,3],3:[4],4:[5],5:[3]})
assert tarjan_scc(6,sadj)==[[0,1,2],[3,4,5]]==kosaraju(6,sadj)
ok("SCC: Tarjan (one pass, low-link) and Kosaraju (two passes) agree")

# ---------- bipartite ----------
def is_bipartite(n, adj):
    color=[0]*n
    for s in range(n):
        if color[s]: continue
        color[s]=1; q=deque([s])
        while q:
            v=q.popleft()
            for w in adj[v]:
                if color[w]==color[v]: return False
                if not color[w]: color[w]=-color[v]; q.append(w)
    return True
b=defaultdict(list,{0:[1,3],1:[0,2],2:[1,3],3:[0,2]})
o=defaultdict(list,{0:[1,2],1:[0,2],2:[0,1]})
assert is_bipartite(4,b) and not is_bipartite(3,o)
ok("bipartite check via 2-colouring BFS")

# ---------- trees ----------
class TN:
    __slots__=("v","l","r")
    def __init__(self,v,l=None,r=None): self.v=v; self.l=l; self.r=r
def build(vals, i=0):
    if i>=len(vals) or vals[i] is None: return None
    return TN(vals[i], build(vals,2*i+1), build(vals,2*i+2))
def level_order(root):
    if not root: return []
    res=[]; q=deque([root])
    while q:
        level=[]
        for _ in range(len(q)):
            n=q.popleft(); level.append(n.v)
            if n.l: q.append(n.l)
            if n.r: q.append(n.r)
        res.append(level)
    return res
def max_depth(root): return 0 if not root else 1+max(max_depth(root.l),max_depth(root.r))
def is_balanced(root):
    def h(n):
        if not n: return 0
        lh=h(n.l)
        if lh<0: return -1
        rh=h(n.r)
        if rh<0 or abs(lh-rh)>1: return -1
        return 1+max(lh,rh)
    return h(root)>=0
def diameter(root):
    best=[0]
    def h(n):
        if not n: return 0
        lh,rh=h(n.l),h(n.r)
        best[0]=max(best[0], lh+rh)
        return 1+max(lh,rh)
    h(root); return best[0]
def lca(root,p,q):
    if not root or root.v in (p,q): return root
    l,r = lca(root.l,p,q), lca(root.r,p,q)
    return root if l and r else (l or r)
def lca_bst(root,p,q):
    while root:
        if p<root.v and q<root.v: root=root.l
        elif p>root.v and q>root.v: root=root.r
        else: return root
    return None
def path_sum_count(root,target):
    from collections import defaultdict as dd
    prefix=dd(int); prefix[0]=1
    def go(n,run):
        if not n: return 0
        run+=n.v
        cnt=prefix[run-target]
        prefix[run]+=1
        cnt+=go(n.l,run)+go(n.r,run)
        prefix[run]-=1                     # undo on the way out: prefix sums on a TREE PATH
        return cnt
    return go(root,0)
def serialize(root):
    res=[]
    def go(n):
        if not n: res.append('#'); return
        res.append(str(n.v)); go(n.l); go(n.r)
    go(root); return ','.join(res)
def deserialize(s):
    it=iter(s.split(','))
    def go():
        v=next(it)
        if v=='#': return None
        n=TN(int(v)); n.l=go(); n.r=go(); return n
    return go()
def right_side_view(root):
    if not root: return []
    res=[]; q=deque([root])
    while q:
        res.append(q[-1].v)
        for _ in range(len(q)):
            n=q.popleft()
            if n.l: q.append(n.l)
            if n.r: q.append(n.r)
    return res
t=build([1,2,3,4,5,6,7])
assert level_order(t)==[[1],[2,3],[4,5,6,7]]
assert max_depth(t)==3 and is_balanced(t) and diameter(t)==4
assert lca(t,4,5).v==2 and lca(t,4,7).v==1
bst=build([8,4,12,2,6,10,14])
assert lca_bst(bst,2,6).v==4 and lca_bst(bst,2,14).v==8
assert right_side_view(t)==[1,3,7]
assert deserialize(serialize(t)) is not None and level_order(deserialize(serialize(t)))==level_order(t)
skew=TN(1,TN(2,TN(3)))
assert not is_balanced(skew)
p=TN(10,TN(5,TN(3),TN(2)),TN(-3,None,TN(11)))
assert path_sum_count(p,8)==2   # paths 5->3 and -3->11
ok("trees: level order, depth, balanced, diameter, LCA (general + BST), path-sum-III, serialize/deserialize, right view")

print("\n".join(out)); print(f"\nALL GRAPH/TREE ASSERTIONS PASSED ({len(out)} groups)")