Algorithm1 Practice10 Interview

Depth-first Search

GuideCode Labs

Explore a branch completely before backtracking, using recursion or an explicit stack. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Depth-first Search when the prompt's constraints and required operations match this shape: Explore a branch completely before backtracking, using recursion or an explicit stack.

On this page · Follow One Branch to Completion

Checking your account…

Follow One Branch to Completion

Depth-first search commits to one neighbor path until it ends, then returns to the most recent unfinished choice. A recursive call stack or an explicit stack owns that frontier.

Define the DFS Frame

Each frame needs a node plus the state required below it: parent, depth, path aggregate, or traversal phase. State the return contract before descending so postorder work has a precise meaning.

Trace DFS Frames

Reference

def dfs_frame_trace(adjacency, start):
    if start == -1: return []
    trace = []
    seen = set()
    def visit(node, depth):
        seen.add(node)
        trace.append([node, depth])
        for neighbor in adjacency[node]:
            if neighbor not in seen:
                visit(neighbor, depth + 1)
    visit(start, 0)
    return trace

Practice

Implement dfs_frame_trace(adjacency, start). Return [node, depth] in recursive preorder, preserving neighbor order and visiting each node once.

def dfs_frame_trace(adjacency, start):
    pass

Public tests

Carry depth in each frame

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Mark Before Descending

In a graph, add a node to visited before exploring neighbors. Marking afterward lets a cycle re-enter the same frame. Trees can sometimes use a parent pointer instead, but only when the input is guaranteed acyclic.

Measure a Connected Component

Reference

def component_size(adjacency, start):
    if start == -1: return 0
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in seen: continue
        seen.add(node)
        stack.extend(adjacency[node])
    return len(seen)

Practice

Implement component_size(adjacency, start). Return the number of nodes reachable from start, or 0 for start -1.

def component_size(adjacency, start):
    pass

Public tests

Ignore cycles and unreachable nodes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Recursive or Iterative DFS

Recursive DFS mirrors the proof and is concise; iterative DFS avoids Python recursion depth and makes traversal phases explicit. Push neighbors in reverse when an explicit stack must reproduce recursive neighbor order. Both take O(V + E).

Explain It in an Interview

Say: “This frame owns one node and this accumulated state. I mark before descending, each edge is considered a bounded number of times, and return means the entire branch is complete.” Include disconnected components and stack-space O(depth).

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Depth-first Search proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Depth-first Search complete workflow	`O(n)`	`O(n)`	Depth-first traversal can carry one immutable scalar state down each branch and record it only at terminal nodes. The running total passed to a node equals the sum from the root through that node, independent of sibling branches.

Space

O(h) recursion depth plus output for the focused Carry State Through Tree DFS implementation.

Assumptions

Adding the current node to its parent total establishes the path sum for that node. Passing the resulting value by argument gives each child the correct prefix while sibling calls cannot mutate one another.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Depth-first Search invariant before coding and preserve it after every update, traversal step, or recursive return.
The frontier contains exactly discovered work that has not yet been fully processed.
Visited state prevents a node or state from being processed through the same role twice.
Depth-first traversal can carry one immutable scalar state down each branch and record it only at terminal nodes. Preserve this claim after every transition.
The running total passed to a node equals the sum from the root through that node, independent of sibling branches. Preserve this claim after every transition.

When To Use Or Avoid Depth-first Search

Use It When

Use Depth-first Search when this precondition is stated or can be proved: The graph or state space has an explicit neighbor relation and repeated states can be identified.
Use it when this maintained state removes repeated work: The frontier contains exactly discovered work that has not yet been fully processed.

Choose Another Tool When

Avoid Depth-first Search when this precondition is absent: The graph or state space has an explicit neighbor relation and repeated states can be identified.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The graph or state space has an explicit neighbor relation and repeated states can be identified.

Avoid

def root_to_leaf_sums(values, children, root):
    pass

Use instead

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        if not children[node]:
            sums.append(total)
            return
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums

Where you will hit this: Carry State Through Tree DFS(opens in a new tab)

Breaking the state transition

Records the running sum at every internal node instead of only when a complete root-to-leaf path ends.

Prevent it: Preserve this proof obligation: Every reachable state enters the frontier under the traversal policy, while visited state prevents duplicate work.

Avoid

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        sums.append(total)
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums

Use instead

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        if not children[node]:
            sums.append(total)
            return
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums

Where you will hit this: Carry State Through Tree DFS(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        sums.append(total)
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums

Use instead

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        if not children[node]:
            sums.append(total)
            return
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums

Where you will hit this: Count Good Nodes in a Binary Tree(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python Compound Statements — Function Definitions(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…