Amazon SDE1 Interview | 55LPA CTC | 2026 Grad | OffCampus
This was the question asked in the interview :-
You are given a binary tree containing N nodes.
A subset of nodes is called valid if no two selected nodes are directly connected by an edge.
Your task is to determine the total number of valid subsets that can be formed from the given binary tree.
The empty subset is also considered valid.
Input
The binary tree is given as a collection of nodes where each node contains:
An integer value.
A pointer/reference to its left child.
A pointer/reference to its right child.
You may assume that the given structure is a valid binary tree.
Output
Return the total number of valid subsets.
Example
Consider the following binary tree:
Node-1 is the root :-
1->left=2
1->right=3
2->left=4
2->right=5
Some valid subsets are:
{}
{1}
{2}
{3}
{4}
{5}
{1,4}
{1,5}
{2,3}
{3,4}
{3,5}
{3,4,5}
A subset such as:
{1,2}
is invalid because nodes 1 and 2 are directly connected.
Similarly:
{2,4}
is invalid because nodes 2 and 4 are directly connected.
Constraints
1 ≤ N ≤ 2 × 10^5
The answer can be very large, so return the answer modulo 10^9 + 7.


