Table of Contents
Problem Statement
The problem “Check if two nodes are on the same path in a Tree” states that you are given a n-ary tree (directed acyclic graph) rooted at root node with uni-directional edges between it’s vertices. You are also given a list of queries q.
- Each query in list q consists of two vertices u & v.
- You have to print “YES” if nodes u & v lie along same path originating from root vertex.
- Else print “NO” if nodes u & v lie along different paths originating from root vertex.
Example
Approach to Check if two nodes are on the same path in a Tree
The idea is to perform DFS from root node. This DFS traversal first visits each subtree of the root until the last depth, meaning that it visits each unique linear path till the last leaf vertex and then moves on to the next linear path.
Consider,
Intime – intime of a node is the time at which it is visited first while performing DFS traversal starting from root node, it’s the entry time of a node during DFS traversal.
Outtime – outtime of a node is the time at which it is visited after all it’s children have been visited, this happens while returning along the path towards root node, it’s exit time of a node during DFS traversal.
If nodes u & v lie along the same path:
- assuming u is parent of v then, intime of u < intime of v & outtime of u > outtime of v.
- Or assuming v is parent of u then, intime of v < intime of u & outtime of v > outtime of u.
- Generally, when two nodes lie along the same path, one is parent and other is child. In that case after DFS traversal:
- intime of parent < intime of child
- outtime of parent > outtime of child
1. Perform DFS traversal from the given root node and for each node calculate entry time and exit time using intime[ ] and outtime[ ] arrays. 2. So after the DFS traversal is complete. Process the query list q. Each query in q consists of two values u and v. 3. If intime[u] < intime[v] and also outtime[u] > outtime[v], print "YES". 4. Or if intime[v] < intime[u] and also outtume[v] > outtime[u], print "YES". 5. If conditions 3 and 4 are false, then print "NO". 6. If conditions 3 and 4 are true, this signifies that u & v lie along the same path originating from the root. 7. If condition 5 is true, then it signifies that u & v do not lie along the same path originating from the root.
The algorithm is depicted below:
Code
C++ Program to Check if two nodes are on the same path in a Tree
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* variable to keep track of intime
and outtime values for each vertex */
int times = 0;
/* function to perform DFS from root nodes to all the leaves
& calculate entry time (intime)
& exit time (outtime)
for each vertex */
void DFS(int root,vector <int> graph[],vector <int> &intime,vector<int> &outtime)
{
intime[root] = ++times;
for(auto i : graph[root])
DFS(i,graph,intime,outtime);
outtime[root] = ++times;
return;
}
/* function that returns true if nodes u and v
lie along the same path else return false */
bool query(int u,int v,vector <int> intime,vector <int> outtime)
{
return ((intime[u] < intime[v] && outtime[u] > outtime[v]) ||
(intime[v] < intime[u] && outtime[v] > outtime[u]));
}
int main()
{
/* Define
1.number of vertices
2.root vertex
3.edges
*/
int V = 9;
int root = 0;
vector<vector<int>> Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
/* construct the graph */
vector <int> graph[V];
for(auto edge : Edges)
graph[edge[0]].push_back(edge[1]);
/* Define vectors that store entry time(intime) &
exit time(outtime) for each vertex of the tree */
vector <int> intime(V,0);
vector <int> outtime(V,0);
/* perform DFS traversal to fill intime & outtime vectors */
DFS(root,graph,intime,outtime);
/* Define query vertices */
vector<vector<int>> q = {{0,5},{2,7},{1,8}};
for(auto i : q)
{
if(query(i[0],i[1],intime,outtime))
cout<<"YES";
else
cout<<"NO";
cout<<endl;
}
return 0;
}YES YES NO
Java code to find Check if two nodes are on the same path in a Tree
import java.io.*;
import java.util.*;
class TutorialCup
{
/* variable to keep track of intime
and outtime values for each vertex */
static int times = 0;
/* function to perform DFS from root nodes to all the leaves
& calculate entry time (intime)
& exit time (outtime)
for each vertex */
static void DFS(int root,ArrayList<ArrayList<Integer>> graph,int [] intime,int [] outtime)
{
intime[root] = ++times;
Iterator itr = graph.get(root).iterator();
while(itr.hasNext())
{
int i = (Integer)itr.next();
DFS(i,graph,intime,outtime);
}
outtime[root] = ++times;
return;
}
/* function that returns true if nodes u and v
lie along the same path else return false */
static boolean query(int u,int v,int [] intime,int [] outtime)
{
return ((intime[u] < intime[v] && outtime[u] > outtime[v]) ||
(intime[v] < intime[u] && outtime[v] > outtime[u]));
}
public static void main (String[] args)
{
/* Define
1.number of vertices
2.root vertex
3.edges
*/
int V = 9;
int root = 0;
int [][] Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
/* construct the graph */
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<V;i++)
graph.add(new ArrayList<Integer>());
for(int i=0; i<Edges.length; i++)
graph.get(Edges[i][0]).add(Edges[i][1]);
/* Define vectors that store entry time(intime) &
exit time(outtime) for each vertex of the tree */
int [] intime = new int[V];
int [] outtime = new int[V];
/* perform DFS traversal to fill intime & outtime vectors */
DFS(root,graph,intime,outtime);
/* Define query vertices */
int [][] q = {{0,5},{2,7},{1,8}};
for(int i=0; i<q.length; i++)
{
if(query(q[i][0],q[i][1],intime,outtime))
System.out.println("YES");
else
System.out.println("NO");
}
}
}YES YES NO
Complexity Analysis
Time complexity
T(n) = O(n), n = number of nodes. Because we have used DFS which has traversed over the nodes in the tree. So the time complexity is linear.
Space Complexity
A(n) = O(n), for using intime[ ] and outtime[ ] arrays. Both of these arrays’ size is dependent on the number of nodes. Thus the space complexity is also linear.