## Wednesday, June 15, 2016

### Check if two nodes are on same path in a tree - GeeksforGeeks

Check if two nodes are on same path in a tree - GeeksforGeeks
Given a tree (not necessarily a binary tree) and a number of queries such that every query takes two nodes of tree as parameters. For every query pair, find if two nodes are on the same path from root to the bottom.
For example, consider the below tree, if given queries are (1, 5), (1, 6) and (2, 6), then answers should be true, true and false respectively.

// To keep track of visited vertices in DFS
bool visit[MAX] = {0};

// To store start and end time of all vertices
// during DFS.
int intime[MAX];
int outtime[MAX];

// initially timer is zero
int timer = 0;

// Does DFS of given graph and fills arrays
// intime[] and outtime[]. These arrays are used
void dfs(vector<int> graph[], int v)
{
visit[v] = true;

// Increment the timer as you enter
// the recursion for v
++timer;

// Upgrade the in time for the vertex
intime[v] = timer;

vector<int>::iterator it = graph[v].begin();
while (it != graph[v].end())
{
if (visit[*it]==false)
dfs(graph, *it);
it++;
}

// increment the timer as you exit the
// recursion for v
++timer;

// upgrade the outtime for that node
outtime[v] = timer;
}

// Returns true if 'u' and 'v' lie on same root to leaf path
// else false.
bool query(int u, int v)
{
return ( (intime[u]<intime[v] && outtime[u]>outtime[v]) ||
(intime[v]<intime[u] && outtime[v]>outtime[u]) );
}
Read full article from Check if two nodes are on same path in a tree - GeeksforGeeks