Skip to main content
Talentd

Sum of Perfect Square Ancestors - Solution & Explanation

HardArrayHash TableMathTree5 min readAsked at: Amazon, Google, Meesho
Practice this problem

Problem Statement

You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.

You are also given an integer array nums, where nums[i] is the positive integer assigned to node i.

Define a value ti as the number of ancestors of node i such that the product nums[i] * nums[ancestor] is a perfect square.

Return the sum of all ti values for all nodes i in range [1, n - 1].

Note:

  • In a rooted tree, the ancestors of node i are all nodes on the path from node i to the root node 0, excluding i itself.

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], nums = [2,8,2]

Output: 3

Explanation:

i Ancestors nums[i] * nums[ancestor] Square Check ti
1 [0] nums[1] * nums[0] = 8 * 2 = 16 16 is a perfect square 1
2 [1, 0] nums[2] * nums[1] = 2 * 8 = 16
nums[2] * nums[0] = 2 * 2 = 4		 Both 4 and 16 are perfect squares 2

Thus, the total number of valid ancestor pairs across all non-root nodes is 1 + 2 = 3.

Example 2:

Input: n = 3, edges = [[0,1],[0,2]], nums = [1,2,4]

Output: 1

Explanation:

i Ancestors nums[i] * nums[ancestor] Square Check ti
1 [0] nums[1] * nums[0] = 2 * 1 = 2 2 is not a perfect square 0
2 [0] nums[2] * nums[0] = 4 * 1 = 4 4 is a perfect square 1

Thus, the total number of valid ancestor pairs across all non-root nodes is 1.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[1,3]], nums = [1,2,9,4]

Output: 2

Explanation:

i Ancestors nums[i] * nums[ancestor] Square Check ti
1 [0] nums[1] * nums[0] = 2 * 1 = 2 2 is not a perfect square 0
2 [0] nums[2] * nums[0] = 9 * 1 = 9 9 is a perfect square 1
3 [1, 0] nums[3] * nums[1] = 4 * 2 = 8
nums[3] * nums[0] = 4 * 1 = 4		 Only 4 is a perfect square 1

Thus, the total number of valid ancestor pairs across all non-root nodes is 0 + 1 + 1 = 2.

 

Constraints:

  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ui, vi]
  • 0 <= ui, vi <= n - 1
  • nums.length == n
  • 1 <= nums[i] <= 105
  • The input is generated such that edges represents a valid tree.

Approach Overview

Problem Overview: You are given a tree where each node contains an integer value. For every node, consider its ancestors along the path to the root. The task is to accumulate the contribution of ancestors whose values are perfect squares and compute the required total efficiently.

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

The direct method checks every node and walks upward through its ancestor chain. For each ancestor, test whether the value is a perfect square using sqrt(x) and verify r * r == x. If the check passes, include it in the running sum. In the worst case (a skewed tree), each node scans up to n ancestors, giving O(n^2) time and O(h) recursion or stack space. This approach is useful for understanding the requirement but quickly becomes too slow for large trees.

Approach 2: DFS with Running Perfect-Square Count (O(n) time, O(h) space)

A more efficient strategy processes the tree using Depth-First Search. While traversing from root to leaves, maintain the contribution from ancestors that are perfect squares. At each node, check whether its value is a square using a constant-time number theory test (int r = sqrt(val)). If it is, update the running sum before exploring children. Each node receives the accumulated value from its parent and passes an updated value to its children. Because each node is visited once and ancestor information is carried forward instead of recomputed, the algorithm runs in O(n) time with O(h) recursion depth.

Approach 3: DFS with Hash Tracking and Number Theory Precheck (O(n) time, O(h) space)

If node values repeat frequently, you can cache square checks in a hash table. Before traversal, determine whether each unique value is a perfect square and store the result. During DFS, look up the value instead of recomputing the square root. This removes repeated math operations and helps when value ranges are large. The traversal logic stays the same: maintain the running ancestor contribution while descending the tree. Concepts from number theory ensure that the square check remains constant time.

Recommended for interviews: The DFS propagation approach is what interviewers expect. It shows that you understand tree traversal, path state propagation, and how to avoid recomputing ancestor relationships. Mentioning the brute force solution demonstrates baseline reasoning, but the optimized DFS solution proves you can reduce repeated work and achieve linear time.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Ancestor TraversalO(n^2)O(h)Small trees or initial reasoning during interviews
DFS with Running Perfect-Square CountO(n)O(h)General optimal solution for most constraints
DFS with Hash Cached Square ChecksO(n)O(h + u)When node values repeat and avoiding repeated sqrt checks improves performance

Video Solution

Sum of Perfect Square Ancestors | LeetCode 3715 | Tree DP • Sanyam IIT Guwahati • 958 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Sum of Perfect Square Ancestors easy or hard?
The problem is generally classified as Hard because it combines multiple concepts: tree traversal, ancestor path management, and number theory checks. The difficulty comes from maintaining path state efficiently while avoiding repeated ancestor scans.
Sum of Perfect Square Ancestors Python/Java solution
Most implementations use recursive DFS. Each function call receives the running contribution from ancestors, checks whether the current node value is a perfect square, updates the state, and then explores child nodes. This pattern translates cleanly to Python, Java, C++, and Go with identical O(n) complexity.
How to solve Sum of Perfect Square Ancestors in O(n)?
Traverse the tree using DFS and carry a running sum or count of ancestors whose values are perfect squares. At each node, check if its value is a square using sqrt and update the running state before visiting its children. Since the ancestor contribution is passed down the recursion instead of recomputed, the total work remains linear.
What is the best approach for Sum of Perfect Square Ancestors?
The most efficient approach uses Depth-First Search while propagating information about perfect-square ancestors along the current root-to-node path. Each node receives the accumulated contribution from its parent and updates it if its value is a perfect square. This avoids repeatedly scanning ancestor chains and runs in O(n) time with O(h) recursion space.
Is Sum of Perfect Square Ancestors asked at Google/Amazon/Meta?
Problems combining tree traversal with number theory checks commonly appear in interviews at companies like Google, Amazon, and Meta. Variants often involve ancestor tracking, path-based aggregation, or mathematical conditions such as primes or perfect squares during DFS.
What data structure is used in Sum of Perfect Square Ancestors?
The core data structure is a tree, typically represented with adjacency lists. The solution relies on depth-first search for traversal and may optionally use a hash table to cache perfect-square checks for repeated values.
What is the time complexity of Sum of Perfect Square Ancestors?
The optimal DFS solution runs in O(n) time because every node in the tree is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack used during depth-first traversal.

Ready to solve this problem?

Practice Sum of Perfect Square Ancestors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays