Count Valid Paths in a Tree - Video Solutions

Problem Overview: You are given a tree with n nodes labeled from 1..n. A path is valid if it contains exactly one prime-numbered node. The task is to count all such paths. Because the structure is a tree, every pair of nodes has exactly one simple path, which lets you reason about paths through prime nodes.

Approach 1: DFS Traversal with Path Prime Check (O(n log log n) time, O(n) space)

Start by precomputing all prime numbers up to n using the Sieve of Eratosthenes. The key observation: every valid path must include exactly one prime node, so treat each prime node as the “center” of potential paths. For each prime node, run DFS into its neighboring components but only traverse non-prime nodes. Each DFS returns the size of a connected component of non-prime nodes attached to that prime.

Suppose the component sizes are s1, s2, s3.... Any pair of nodes chosen from two different components forms a valid path that passes through the prime node. You also count single-ended paths from the prime to each non-prime node. Accumulate combinations using a running prefix sum to avoid quadratic merging. The algorithm performs a single traversal per component and uses adjacency lists for the tree. This approach relies heavily on Depth-First Search and basic Number Theory for prime detection.

Approach 2: Dynamic Programming on Tree (Tree DP) (O(n log log n) time, O(n) space)

This version computes path counts during a single DFS using dynamic programming on the tree. For every node, maintain two states: paths in its subtree that contain 0 primes and paths that contain 1 prime. When merging a child subtree into the parent, combine states carefully so the resulting path still contains exactly one prime.

If the current node is non-prime, zero-prime paths extend normally, and one-prime paths can be formed by attaching a subtree that already contains one prime. If the current node is prime, any extension immediately introduces the single allowed prime, so you only combine with zero-prime child paths. Each merge step contributes new valid paths to the global answer.

This technique avoids explicitly iterating over components for each prime node. Instead, it pushes information upward during DFS. The method is typical Dynamic Programming on a Tree, where each node summarizes information from its children before returning to its parent.

Recommended for interviews: The DFS component-count approach is the most common solution. It shows that you recognized the “exactly one prime” constraint and converted the problem into counting combinations of non-prime components around a prime node. The Tree DP approach is equally optimal but more complex to reason about under time pressure. Demonstrating the DFS solution first and discussing the DP variant shows strong algorithmic depth.