Tree of Coprimes: DFS with Ancestor Tracking

You are given a tree rooted at node 0, where each node i has a value nums[i] between 1 and 50. For each node, you need to find the closest ancestor whose value is coprime with that node's value (meaning their greatest common divisor is 1). Return an array ans where ans[i] is the index of the closest coprime ancestor of node i, or -1 if no such ancestor exists.

This is LeetCode 1766: Tree of Coprimes, and the trick is to exploit the small value range. There are only 50 possible values, so you do not need to check every ancestor individually. You only need to check which of the 50 values are coprime with the current node, then look up the deepest ancestor that holds one of those values.

Why this problem matters

Tree of Coprimes combines two skills that show up in harder interview problems: DFS on a general tree with backtracking, and precomputation to avoid redundant work. The naive approach of checking every ancestor for every node is O(n^2) in the worst case, which fails for large trees. The optimized approach runs in O(50n), which is effectively linear.

This problem teaches you to ask: "Is there a small, bounded set of values I can precompute against?" When a problem constrains values to a small range while allowing the data structure itself to be large, that gap is almost always the key insight. You will see the same pattern in problems involving frequencies, bounded alphabets, and fixed-range constraints.

The key insight

Since node values range from 1 to 50, you can precompute a lookup table: for each value v from 1 to 50, store the list of all values from 1 to 50 that are coprime with v. This precomputation takes O(50 * 50) = O(2500) time, which is nothing.

During DFS, maintain a dictionary that maps each value (1 to 50) to the most recent ancestor node with that value, along with its depth. When you visit a node with value v:

1. Look up all values coprime with v from the precomputed table
2. For each coprime value, check if there is an ancestor with that value in the dictionary
3. Among all matching ancestors, pick the one with the greatest depth (closest to the current node)
4. Before recursing into children, save the current entry in the dictionary for value v, then overwrite it with the current node
5. After returning from all children, restore the old entry (backtracking)

This way, you check at most 50 values per node instead of potentially thousands of ancestors.

The solution

from math import gcd
from collections import defaultdict

def get_coprimes(nums: list[int], edges: list[list[int]]) -> list[int]:
    n = len(nums)
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    coprime_vals = defaultdict(list)
    for i in range(1, 51):
        for j in range(1, 51):
            if gcd(i, j) == 1:
                coprime_vals[i].append(j)

    ans = [-1] * n
    ancestor = {}

    def dfs(node, parent, depth):
        val = nums[node]
        best_depth = -1
        best_node = -1

        for cp in coprime_vals[val]:
            if cp in ancestor:
                anc_node, anc_depth = ancestor[cp]
                if anc_depth > best_depth:
                    best_depth = anc_depth
                    best_node = anc_node

        ans[node] = best_node
        old = ancestor.get(val)
        ancestor[val] = (node, depth)

        for child in adj[node]:
            if child != parent:
                dfs(child, node, depth + 1)

        if old is not None:
            ancestor[val] = old
        else:
            del ancestor[val]

    dfs(0, -1, 0)
    return ans

Here is what each section does:

Building the adjacency list. The tree is given as a list of edges, so we convert it to an adjacency list. Since the tree is undirected, each edge adds a neighbor in both directions.

Precomputing coprime pairs. For every value from 1 to 50, we find all values from 1 to 50 that are coprime with it. This gives us a lookup table so we never compute GCD during the main traversal.

The ancestor dictionary. The ancestor dict maps a value to (node_index, depth). At any point during DFS, ancestor[v] holds the most recent ancestor on the current path that has value v. There is at most one entry per value (the deepest one), because we overwrite on the way down and restore on the way up.

Finding the closest coprime ancestor. For the current node's value, we iterate through at most 50 coprime values. For each one present in the ancestor dict, we compare depths and keep the deepest. The deepest ancestor is the closest one in the tree.

Backtracking. Before recursing, we save the old entry for the current value and write the new one. After recursing, we restore the old entry. This ensures the ancestor dict always reflects exactly the current root-to-node path.

Visual walkthrough

Let's trace the algorithm on a tree with 7 nodes where nums = [2, 3, 4, 7, 12, 5, 9]. Watch how the ancestor dictionary changes at each step, and how backtracking restores it when we leave a subtree.

The key observation from this walkthrough: node 5 (val 5) found two coprime ancestors in the dictionary (val 2 at depth 0, val 3 at depth 1) and correctly picked the deeper one (node 1, depth 1). Meanwhile, node 4 (val 12) found nothing coprime in the dictionary because neither 2 nor 3 is coprime with 12. The bounded value range makes these lookups fast, just 50 checks per node regardless of tree size.

Complexity analysis

Time: Building the adjacency list takes O(n). Precomputing coprime pairs takes O(50 * 50) = O(2500). The DFS visits each node once. At each node, we check at most 50 coprime values. Total: O(n + 2500 + 50n) = O(50n), which is effectively O(n).

Space: The adjacency list uses O(n). The ancestor dictionary holds at most 50 entries (one per possible value). The coprime lookup table uses O(50 * 50) = O(2500). The DFS call stack uses O(h) where h is the tree height, which is O(n) in the worst case. Total: O(n).

The building blocks

This problem combines two reusable patterns that CodeBricks drills independently:

1. DFS with backtracking state

The pattern of modifying shared state before recursing into children, then restoring it when you backtrack. The skeleton looks like this:

def dfs(node, parent, depth):
    old = state.get(key)
    state[key] = new_value

    for child in adj[node]:
        if child != parent:
            dfs(child, node, depth + 1)

    if old is not None:
        state[key] = old
    else:
        del state[key]

This pattern shows up whenever you need to track path-specific information during tree DFS. The save-modify-recurse-restore sequence ensures each node only sees ancestors on its own root-to-node path, never nodes from sibling subtrees.

2. Precomputation over a bounded value range

When input values are constrained to a small range (here 1 to 50), you can precompute all pairwise relationships ahead of time. Instead of computing gcd(nums[node], nums[ancestor]) on the fly for every ancestor, you compute all coprime pairs once at the start. This converts an unbounded per-node cost into a fixed O(50) lookup.

The same idea applies to problems with alphabet-sized constraints (26 letters), small digit ranges (0 to 9), or fixed frequency bounds. Always check whether the value domain is small enough to precompute.

Edge cases

• Single node: The tree has only one node. There are no ancestors, so ans[0] = -1.
• Linear tree (skewed): The tree is a straight chain. Each node has exactly one path to the root. The algorithm works the same way, but the call stack depth is O(n). For very deep trees, you might need an iterative DFS to avoid stack overflow.
• All nodes have the same value: If every node has value v, then gcd(v, v) = v. The ancestor is coprime only if v = 1. When v = 1, every ancestor is coprime (pick the closest). When v > 1, no ancestor is coprime, so every answer is -1.
• Node value is 1: The value 1 is coprime with every positive integer. So a node with value 1 will always have a coprime ancestor (the closest ancestor, regardless of its value), unless it is the root.
• Root value is 1: Every direct child of the root will have ans[child] = 0, since gcd(anything, 1) = 1.

From understanding to recall

You have seen the core trick: precompute coprime pairs for the small value range, then use a backtracking dictionary to track the deepest ancestor for each value during DFS. The logic makes sense right now. But in an interview, will you remember to save and restore the ancestor entry? Will you remember to track depth so you can pick the closest coprime ancestor?

Understanding is not recall. The gap between "I see how it works" and "I can write it from scratch under pressure" is what spaced repetition fills. You practice the save-modify-recurse-restore skeleton and the precomputation loop separately. After a few rounds, you can reconstruct the full solution without second-guessing any detail.

Tree problems with backtracking state are a category, not a one-off trick. Once you internalize the pattern, problems like Tree of Coprimes, path sum variants, and ancestor queries all feel like variations on the same theme.

Related posts

• Lowest Common Ancestor of a Binary Tree - Another tree problem that requires understanding ancestor relationships during DFS traversal
• Course Schedule - Graph DFS with state tracking, teaches the three-color marking pattern that parallels the ancestor dictionary here
• Binary Tree Maximum Path Sum - Post-order DFS with global state, the same "return one thing, track another" idea applied to a different problem

CodeBricks breaks Tree of Coprimes into its DFS-with-backtracking and bounded-value-precomputation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a hard tree problem shows up in your interview, you do not scramble to remember the details. You just write it.