Very easy O(n) solution using only arrays


#1
int Solution::solve(int A, vector<vector<int> > &B) 
{
    if(A<=3)
        return 0;
    //to store parent of each node i
    int parent[A+1]={0};
    parent[1]=-1;
    //to store number of edges in the subtree with root i
    int edges[A+1]={0};
    for(int i=0;i<B.size();i++)
    {
        parent[B[i][1]]=B[i][0];
        edges[B[i][0]]++;
    }
    for(int i=A;i>1;i--)
        edges[parent[i]]+=edges[i];
    int ans=0;
    
    for(int i=2;i<=A;i++)
    {
        if(edges[i]%2==1)
            ans++;
    }
    return ans;
}

#2

Explanation for this approach:

We need to count the number of maximum edges that can be removed.
Can this be equivalent to number of subtrees with even nodes ??

Now our task is to find subtrees with even nodes. This can be calculated as number of subtrees with odd number of edges.

i.e. number of nodes in a tree=number of edges+1

Now parent array is used to stare parent of each node.
edges array is used to store number of edges in a particular tree.

In this code
for(int i=0;i<B.size();i++)
{
parent[B[i][1]]=B[i][0];
edges[B[i][0]]++;
}
we are actually adding all the edges that are directly connected to a particular node(node[i] in this case)

for(int i=A;i>1;i–)
edges[parent[i]]+=edges[i];

by this we are adding all the edges directly or indirectly connected to node i

Now in the last part we are just checking whether a particular node has odd or even edges, if it has odd edges , it is a even subtree


#3

The answer is really good but unfortunately, it’s flawed. The code assumes that the parent nodes necessarily have value less than child node which may not be the case. Although the code gets accepted on interviewbit but there are many test-cases in which this code will fail.