Skip to main content
Talentd

Tree of Coprimes - Solution & Explanation

HardArrayMathTreeDepth-First Search19 min readAsked at: Google
Practice this problem

Problem Statement

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node's value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

 

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

 

Constraints:

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

Approach Overview

Problem Overview: You are given a tree where each node contains a value. For every node, return the closest ancestor whose value is coprime with the current node's value. If no such ancestor exists, return -1. The challenge is efficiently searching ancestors while traversing the tree.

Approach 1: Brute Force Ancestor Scan (O(n^2) time, O(n) space)

Traverse the tree and, for each node, walk up its ancestor chain until reaching the root. At every step compute gcd(nodeValue, ancestorValue). The first ancestor with gcd == 1 is the answer. This approach relies on parent pointers or storing the current path during a Depth-First Search. The problem is worst‑case complexity: a skewed tree may require scanning up to n ancestors for each node, producing O(n^2) time.

Approach 2: DFS with Coprime Value Tracking (O(n * 50) time, O(n + 50) space)

The optimized solution leverages the constraint that node values are small (1–50). Precompute which values are coprime with each other using gcd from number theory. During a DFS traversal of the tree, maintain an array of stacks indexed by value (1..50). Each stack stores nodes with that value along the current root‑to‑node path along with their depths.

When visiting a node with value v, iterate through all values 1..50 that are coprime with v. For each candidate value, check the most recent node in its stack (the deepest ancestor with that value). Track the ancestor with the maximum depth and record it as the answer. After processing the node, push it onto the stack corresponding to its value, explore children recursively using DFS, then pop it when backtracking.

This technique turns the ancestor search into a constant‑bounded scan over 50 possible values rather than scanning the entire path. Each node performs at most 50 checks, giving O(n * 50) time which behaves like linear time in practice. The extra space comes from recursion plus the value stacks.

Recommended for interviews: The DFS with coprime value tracking is the expected solution. Interviewers want to see two insights: modeling the graph as a DFS traversal and exploiting the small value range (≤50) to avoid scanning the full ancestor path. Mentioning the brute force ancestor scan first shows understanding of the problem before optimizing it.

Approach 1: Approach 1: Depth-First Search with GCD Check

This method utilizes a depth-first search (DFS) algorithm to traverse the tree. For each node, we check its ancestors to find the closest ancestor that is coprime with the current node. We make use of a stack to backtrack when necessary and a map to keep track of potential coprime ancestors.

This solution uses a DFS recursively over nodes of the tree, passing the current node's value to check against ancestors stored in `coprime_ancestors`. Ancestors' indices are stored for reference if they meet the coprime condition. GCD is computed for all values to determine coprimeness. The complexity is efficiently handled due to the limited scope of values (1-50), allowing constant-time updates and lookups in the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes, as we perform DFS.
Space Complexity: O(n + 50), i.e., O(n) for results and coprime ancestors map.

Try this approach in the editor →

Approach 2: Preprocessing + Enumeration + Stack + Backtracking

Since the range of nums[i] in the problem is [1, 50], we can preprocess all the coprime numbers for each number and record them in the array f, where f[i] represents all the coprime numbers of i.

Next, we can use a backtracking method to traverse the entire tree from the root node. For each node i, we can get all the coprime numbers of nums[i] through the array f. Then we enumerate all the coprime numbers of nums[i], find the ancestor node t that has appeared and has the maximum depth, which is the nearest coprime ancestor node of i. Here we can use a stack array stks of length 51 to get each appeared value v and its depth. The top element of each stack stks[v] is the nearest ancestor node with the maximum depth.

The time complexity is O(n times M), and the space complexity is O(M^2 + n). Where n is the number of nodes, and M is the maximum value of nums[i], in this problem M = 50.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Depth-First Search with GCD Check

Time Complexity: O(n), where n is the number of nodes, as we perform DFS.
Space Complexity: O(n + 50), i.e., O(n) for results and coprime ancestors map.

Preprocessing + Enumeration + Stack + Backtracking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Ancestor Scan with GCDO(n^2)O(n)Conceptual baseline or when constraints are very small
DFS with Coprime Value StacksO(n * 50)O(n + 50)Optimal solution for large trees; leverages limited value range

Video Solution

LeetCode 1766. Tree of Coprimes | Biweekly Contest 46 | Hard | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 1,446 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Tree of Coprimes easy or hard?
Tree of Coprimes is rated Hard because it combines multiple concepts: tree traversal, ancestor tracking, and number theory with GCD. The key difficulty is avoiding an O(n^2) ancestor search by exploiting the limited value range.
Tree of Coprimes Python/Java solution
Implement a DFS that maintains stacks indexed by node value. Before exploring children, determine the nearest coprime ancestor by scanning stacks of compatible values. The same logic works in Python, Java, C++, and JavaScript with minor syntax differences.
How to solve Tree of Coprimes in O(n)?
Treat the tree traversal as DFS while keeping stacks of ancestors grouped by value. Because node values are limited to 1–50, you only examine values coprime with the current node instead of scanning all ancestors. This limits work per node to a small constant factor, making the algorithm effectively linear.
What is the best approach for Tree of Coprimes?
The most efficient approach uses Depth-First Search with value tracking. Maintain stacks for each value (1–50) representing ancestors on the current DFS path. For every node, check stacks of values that are coprime with its value and choose the deepest ancestor. This reduces the search to at most 50 checks per node.
Is Tree of Coprimes asked at Google/Amazon/Meta?
Tree and number theory problems similar to Tree of Coprimes appear in interviews at companies like Google, Amazon, and Meta. Interviewers often test DFS traversal combined with mathematical constraints such as GCD or coprime checks.
What data structure is used in Tree of Coprimes?
The solution uses an adjacency list for the tree, recursion or a stack for DFS traversal, and 50 auxiliary stacks (or arrays) to track the most recent ancestor for each value. A GCD function from number theory determines whether two values are coprime.
What is the time complexity of Tree of Coprimes?
The optimized DFS solution runs in O(n * 50) time where n is the number of nodes. Each node checks at most 50 possible coprime values. Space complexity is O(n + 50) due to recursion and stacks storing ancestors along the path.

Ready to solve this problem?

Practice Tree of Coprimes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays