Sum of Perfect Square Ancestors - Solution & Explanation

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.