 # ALTRTREE - Editorial (Kodeathon 15.2)

Practice

Contest

Author & Editorialist: Pulkit Sharma

Tester: Satyam Gupta

EASY

Graphs, (DFS)

### PROBLEM:

Given a Tree , find whether whether all the nodes of a tree satisfy the condition to make it an alternating tree. Read here to see details.

### EXPLANATION:

let state store the state at which the current node is. There are two possible states . crest or trough.

What the problem boils down is to find whether all the paths from root to the leaves is of the form [crest,trough,crest,...] or [trough,crest,trough...] .

This can easily be done using DFS.

To start with DFS , we first need to find the state of the root node.
This can be done by comparing it with its children.

If all the child nodes have a value greater than the root , then the root's state is trough , stored as 0.

Similarly, if all the child nodes have a value less than the root, then the root's state is crest , stored as 1.

If none of the above is true , then the root is in an invalid state.
So, straightaway the tree is Not an Alternating Tree.

Once we have the root's state, we can start with our DFS . But we need to slightly modify the standard DFS implementation as we have to keep track of the state of the current node the DFS has reached.

``````	DFS(node,state)
//other necessary code
if state = 0
//every child should be greater than it
for all children
if(child_i is greater than node)
DFS(child_i,1-state) //IMPORTANT , change the state
else
//exit from DFS, not an alternating Tree

if state = 1
//every child should be smaller than it
for all children
if(child_i is smaller than node)
DFS(child_i,1-state) //IMPORTANT , change the state
else
//exit from DFS, not an alternating Tree
``````

If the DFS did not prematurely end, then depending upon the state of the root we can print our answer.

If the DFS did end prematurely , then the tree is not an Alternating Tree

### AUTHOR’S SOLUTION:

``````#include<iostream>
#include<list>
#include<vector>
#include<cstdio>

using namespace std;

int a;
vector< list<int> > g(10005);
bool notset,mat,nat;

void dfs(int x,bool y)
{
for(list<int>::iterator it=g[x].begin();!nat && it!=g[x].end();it++)
{
if(notset)
{
if(a[x]<a[*it]) mat=1;
else y=mat=0;
notset=0;
}
else
{
if((!y && a[x]<a[*it])||(y && a[x]>a[*it]))
{nat=1;return;}
}

//printf("\n[%d,%d] (%d,%d,%d)",x,*it,notset,mat,nat);

dfs(*it,!y);

}

}

int main()
{
cin.sync_with_stdio(false);
cin.tie(NULL);

int t,i,j,n,x,y;
cin>>t;

while(t--)
{
cin>>n;

for(i=0;i<n;i++){cin>>a[i];g[i].clear();}

nat=0;
notset=1;
for(i=0;i<n;i++)
{
cin>>x;

for(j=0;j<x;j++)
{
cin>>y;

g[i].push_back(y);
}
}

dfs(0,1);

if(nat) cout<<"NAT\n";
else if(mat) cout<<"MAT\n";
else cout<<"VAT\n";

}

return 0;
}
``````
//