Count Non Adjacent Subsets in a Rooted Tree - Solution & Explanation

Q: Is Count Non Adjacent Subsets in a Rooted Tree easy or hard?

The problem is generally classified as Hard because it requires recognizing the independent set structure and designing a two‑state DP on trees. The implementation itself is straightforward once the recurrence is identified, but deriving the correct DP transition often challenges candidates.

Q: Count Non Adjacent Subsets in a Rooted Tree Python/Java solution

Implement DFS on the tree and return two values per node: include and exclude. In Python, recursion with adjacency lists is common, while Java implementations typically store dp arrays and traverse children using lists. Both versions follow the same recurrence and run in O(n) time with O(n) space.

Q: How to solve Count Non Adjacent Subsets in a Rooted Tree in O(n)?

Run a DFS from the root and compute two DP values for each node: dp[u][0] for excluding the node and dp[u][1] for including it. When including a node, multiply the excluded states of its children. When excluding a node, multiply the sum of included and excluded states for each child. The final answer is dp[root][0] + dp[root][1].

Q: What is the best approach for Count Non Adjacent Subsets in a Rooted Tree?

The optimal approach uses tree dynamic programming with depth‑first search. For each node, compute two states: included and excluded. If a node is included, all children must be excluded; if excluded, children can be either included or excluded. This DFS-based tree DP processes each node once, giving O(n) time complexity and O(n) space.

Q: Is Count Non Adjacent Subsets in a Rooted Tree asked at Google/Amazon/Meta?

Tree DP and independent set problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include maximum independent set in trees, house robber on trees, and counting valid node subsets. This problem tests recognition of the include/exclude DP pattern on trees.

Q: What data structure is used in Count Non Adjacent Subsets in a Rooted Tree?

The solution represents the tree using an adjacency list and processes it with depth‑first search. A DP array or pair of values per node stores the include and exclude counts. This combination of adjacency lists, recursion, and dynamic programming enables linear-time computation.

Q: What is the time complexity of Count Non Adjacent Subsets in a Rooted Tree?

The optimal tree DP solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal, and combining results from children takes constant work per edge. Space complexity is O(n) due to recursion stack and DP storage.

HardArray Dynamic Programming Tree Depth-First Search4 min readAsked at: Infosys

Practice this problem

Problem Statement

You are given a rooted tree with n nodes labeled from 0 to n - 1, represented by an integer array parent of length n, where:

parent[0] = -1 (node 0 is the root).
For each 1 <= i < n, parent[i] is the parent of node i (0 <= parent[i] < i).

You are also given an integer array nums of length n, where nums[i] is the value of node i, and an integer k.

A non-empty subset of nodes is called valid if:

The sum of the values of the selected nodes is divisible by k.
No two selected nodes are adjacent in the tree (no node and its direct parent are both included in the subset).

Return the number of valid subsets modulo 10⁹ + 7.

Example 1:

Input: parent = [-1,0,1], nums = [1,2,3], k = 3

Output: 1

Explanation:

The only valid subset is {2}. It contains node 2 with value 3, which is divisible by 3.

Example 2:

Input: parent = [-1,0,0,0], nums = [2,1,2,1], k = 3

Output: 2

Explanation:

The valid subsets are:

{1, 2}: Nodes 1 and 2 are both children of node 0 and not directly connected to each other. Their values sum to 1 + 2 = 3, which is divisible by 3.
{2, 3}: Nodes 2 and 3 are also non-adjacent. Their values sum to 2 + 1 = 3, which is divisible by 3.

No other subset satisfies both conditions. Therefore, the answer is 2.

Constraints:

n == parent.length == nums.length
1 <= n <= 1000
parent[0] == -1
For all 1 <= i < n:
- 0 <= parent[i] < i
1 <= nums[i] <= 10⁹
1 <= k <= 100
parent describes a valid rooted tree.

Approach Overview

Problem Overview: Given a rooted tree, count how many subsets of nodes can be selected such that no two chosen nodes share a parent–child relationship. In graph terms, this asks for the number of independent sets in a tree.

Approach 1: Brute Force Subset Enumeration (O(2^n * n) time, O(n) space)

Generate every subset of nodes and check whether it contains an adjacent pair. For each subset, iterate through nodes and verify that no node and its parent are both selected. This guarantees correctness but becomes infeasible quickly because a tree with n nodes has 2^n possible subsets. Useful only for very small trees or for validating optimized solutions during testing.

Approach 2: Backtracking with Pruning (O(2^n) worst case, O(n) space)

Traverse nodes and decide whether to include or exclude each one. If you include a node, you must forbid selecting its parent and children. Maintaining a visited or restricted set allows pruning branches early. This reduces some redundant checks compared to full subset enumeration but still explores an exponential search space. Works for small trees where constraints allow aggressive pruning.

Approach 3: Tree Dynamic Programming with DFS (O(n) time, O(n) space)

The optimal solution uses dynamic programming on the tree structure. For each node u, compute two values: dp[u][0] (number of valid subsets in the subtree when u is excluded) and dp[u][1] (when u is included). If u is included, none of its children can be included, so multiply the dp[v][0] values of all children v. If u is excluded, each child can be either included or excluded, so multiply dp[v][0] + dp[v][1]. Compute these values using a depth‑first traversal of the tree with DFS. This structure works because trees have no cycles, making subtrees independent. The final answer is dp[root][0] + dp[root][1]. This technique is a classic example of tree DP.

Recommended for interviews: The DFS + tree DP approach. Interviewers expect you to recognize that the constraint "no adjacent nodes" maps directly to the independent set problem on trees. Starting from a brute force explanation shows you understand the constraint, but deriving the include/exclude DP demonstrates strong problem‑solving skills and knowledge of tree dynamic programming.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Subset Enumeration	O(2^n * n)	O(n)	Very small trees or verifying correctness during testing
Backtracking with Pruning	O(2^n)	O(n)	Small input sizes where pruning significantly reduces the search space
Tree DP with DFS	O(n)	O(n)	General case and interview settings; optimal for large trees

Video Solution

Leetcode 3939 | Count Non Adjacent Subsets in a Rooted Tree | Leetcode biweekly 183 | DP on Trees • CodeWithMeGuys • 575 views views

Frequently Asked Questions

Is Count Non Adjacent Subsets in a Rooted Tree easy or hard?

The problem is generally classified as Hard because it requires recognizing the independent set structure and designing a two‑state DP on trees. The implementation itself is straightforward once the recurrence is identified, but deriving the correct DP transition often challenges candidates.

Count Non Adjacent Subsets in a Rooted Tree Python/Java solution

Implement DFS on the tree and return two values per node: include and exclude. In Python, recursion with adjacency lists is common, while Java implementations typically store dp arrays and traverse children using lists. Both versions follow the same recurrence and run in O(n) time with O(n) space.

How to solve Count Non Adjacent Subsets in a Rooted Tree in O(n)?

Run a DFS from the root and compute two DP values for each node: dp[u][0] for excluding the node and dp[u][1] for including it. When including a node, multiply the excluded states of its children. When excluding a node, multiply the sum of included and excluded states for each child. The final answer is dp[root][0] + dp[root][1].

What is the best approach for Count Non Adjacent Subsets in a Rooted Tree?

The optimal approach uses tree dynamic programming with depth‑first search. For each node, compute two states: included and excluded. If a node is included, all children must be excluded; if excluded, children can be either included or excluded. This DFS-based tree DP processes each node once, giving O(n) time complexity and O(n) space.

Is Count Non Adjacent Subsets in a Rooted Tree asked at Google/Amazon/Meta?

Tree DP and independent set problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include maximum independent set in trees, house robber on trees, and counting valid node subsets. This problem tests recognition of the include/exclude DP pattern on trees.

What data structure is used in Count Non Adjacent Subsets in a Rooted Tree?

The solution represents the tree using an adjacency list and processes it with depth‑first search. A DP array or pair of values per node stores the include and exclude counts. This combination of adjacency lists, recursion, and dynamic programming enables linear-time computation.

What is the time complexity of Count Non Adjacent Subsets in a Rooted Tree?

The optimal tree DP solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal, and combining results from children takes constant work per edge. Space complexity is O(n) due to recursion stack and DP storage.

Ready to solve this problem?

Practice Count Non Adjacent Subsets in a Rooted Tree with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance51.7%

Approaches0

Reading time4 min

Asked at

Infosys