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

// to answer given queries.

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