Given a tree with N nodes and (N-1) edges and source node is at 1st position. There are Q queries, each of the type {pos, X, Y}. Perform the following operation based on the type of the query:
- If pos = 0, then find if Y is present in the subtree of X.
- If pos = 1, then find if X is present in the subtree of Y.
Examples:
Input: N: = 9, edges = {{1, 2}, {1, 3}, {2, 6}, {2, 7}, {6, 9}, {7, 8}, {3, 4}, {3, 5}}
Q = 5, query = {{0, 2, 8}, {1, 2, 8}, {1, 6, 5}, {0, 6, 5}, {1, 9, 1}}
Output: {Yes, No, No, No, Yes}
Explanation: See the image below.
8 is present in the subtree of 2 and 9 is also present in the subtree of 9.
For the other queries it does not satisfy the condition.
Input: N = 2, edges = {{1, 2}}
Q = 1, query = {0, 2, 1}
Output: {No}
Explanation: 1 is not present in the subtree of 2.
Approach: The solution of the problem is based on the DFS. Take in time and out time for each node. Using this it can be easily checked if any node is present in the subtree of other node or not. Follow the steps mentioned below:
- At first, find in time( time at which we are entering at that node) and out time (time at which we are leaving that node ) for each of the nodes (initially our timer is 1) using DFS traversal of the tree.
- Then for each of the queries, according to its type find if Y is present in the subtree of X or vice-versa.
- To check if Y is present in the subtree of X check if in time of Y is more than X and out time of Y is less than X and just the opposite to check if X is present in the subtree of Y.
Below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Initial timer=1int timer = 1;// Simple DFS Functionvoid dfs(vector<int> adj[], int itime[], int otime[], int src, int par){ // While visiting a node // mark its timer in time and // increase timer for next nodes itime[src] = timer++; for (auto it : adj[src]) { if (it != par) { dfs(adj, itime, otime, it, src); } } // While leaving a node // mark its timer in out time // and increase timer for next nodes otime[src] = timer++;}// Check for subtreebool check(int itime[], int otime[], int x, int y){ // Intime of y should be more // and outime should be less than x if (itime[x] < itime[y] && otime[x] > otime[y]) return true; return false;}// Function to solve the queriesvoid solve(int N, vector<vector<int> >& edges, int Q, vector<vector<int> >& query){ vector<int> adj[N + 1]; // N-1 edges given for (int i = 0; i < N - 1; i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } // Array for intime int intime[N + 1]; // Array for outime int outtime[N + 1]; // Using DFS function // to find intime and outtime dfs(adj, intime, outtime, 1, -1); for (int i = 0; i < Q; i++) { int type = query[i][0], X = query[i][1], Y = query[i][2]; if (type == 0) { if (check(intime, outtime, X, Y)) { // To check if Y is present // in subtree of X cout << "Yes" << endl; } else { cout << "No" << endl; } } else { if (check(intime, outtime, Y, X)) { // To check if X is present // in subtree of Y cout << "Yes" << endl; } else { cout << "No" << endl; } } }}// Driver codeint main(){ int N = 9; // N is the number of nodes vector<vector<int> > edges = { { 1, 2 }, { 1, 3 }, { 2, 6 }, { 2, 7 }, { 6, 9 }, { 7, 8 }, { 3, 4 }, { 3, 5 } }; int Q = 5; vector<vector<int> > query = { { 0, 2, 8 }, { 1, 2, 8 }, { 1, 6, 5 }, { 0, 6, 5 }, { 1, 9, 1 } }; solve(N, edges, Q, query); return 0;} |
Java
// Java program to implement the approachimport java.util.*;class GFG{ // Initial timer=1 static int timer = 1; // Simple DFS Function static void dfs(Vector<Integer> adj[], int itime[], int otime[], int src, int par) { // While visiting a node // mark its timer in time and // increase timer for next nodes itime[src] = timer++; for (int it : adj[src]) { if (it != par) { dfs(adj, itime, otime, it, src); } } // While leaving a node // mark its timer in out time // and increase timer for next nodes otime[src] = timer++; } // Check for subtree static boolean check(int itime[], int otime[], int x, int y) { // Intime of y should be more // and outime should be less than x if (itime[x] < itime[y] && otime[x] > otime[y]) return true; return false; } // Function to solve the queries static void solve(int N, int[][] edges, int Q, int[][] query) { Vector<Integer> []adj = new Vector[N + 1]; for (int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); // N-1 edges given for (int i = 0; i < N - 1; i++) { adj[edges[i][0]].add(edges[i][1]); adj[edges[i][1]].add(edges[i][0]); } // Array for intime int []intime = new int[N + 1]; // Array for outime int []outtime = new int[N + 1]; // Using DFS function // to find intime and outtime dfs(adj, intime, outtime, 1, -1); for (int i = 0; i < Q; i++) { int type = query[i][0], X = query[i][1], Y = query[i][2]; if (type == 0) { if (check(intime, outtime, X, Y)) { // To check if Y is present // in subtree of X System.out.print("Yes" +"\n"); } else { System.out.print("No" +"\n"); } } else { if (check(intime, outtime, Y, X)) { // To check if X is present // in subtree of Y System.out.print("Yes" +"\n"); } else { System.out.print("No" +"\n"); } } } } // Driver code public static void main(String[] args) { int N = 9; // N is the number of nodes int[][] edges = { { 1, 2 }, { 1, 3 }, { 2, 6 }, { 2, 7 }, { 6, 9 }, { 7, 8 }, { 3, 4 }, { 3, 5 } }; int Q = 5; int[][] query = { { 0, 2, 8 }, { 1, 2, 8 }, { 1, 6, 5 }, { 0, 6, 5 }, { 1, 9, 1 } }; solve(N, edges, Q, query); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement the approachimport collections# Initial timer=1timer = 1# Simple DFS Functiondef dfs(adj, itime, otime, src, par): global timer # While visiting a node # mark its timer in time and # increase timer for next nodes itime[src] = timer timer += 1 for it in adj[src]: if it != par: dfs(adj, itime, otime, it, src) # While leaving a node # mark its timer in out time # and increase timer for next nodes otime[src] = timer timer += 1# Check for subtreedef check(itime, otime, x, y): # Intime of y should be more # and outime should be less than x if itime[x] < itime[y] and otime[x] > otime[y]: return True return False# Function to solve the queriesdef solve(N, edges, Q, query): adj = [collections.deque() for _ in range(N + 1)] # N-1 edges given for i in range(N - 1): adj[edges[i][0]].append(edges[i][1]) adj[edges[i][1]].append(edges[i][0]) # Array for intime intime = [0] * (N + 1) # Array for outime otime = [0] * (N + 1) # Using DFS function # to find intime and outime dfs(adj, intime, otime, 1, -1) for i in range(Q): type, X, Y = query[i] if type == 0: if check(intime, otime, X, Y): # To check if Y is present # in subtree of X print("Yes") else: print("No") else: if check(intime, otime, Y, X): # To check if X is present # in subtree of Y print("Yes") else: print("No")# Driver codeif __name__ == "__main__": N = 9 # N is the number of nodes edges = [ [1, 2], [1, 3], [2, 6], [2, 7], [6, 9], [7, 8], [3, 4], [3, 5] ] Q = 5 query = [ [0, 2, 8], [1, 2, 8], [1, 6, 5], [0, 6, 5], [1, 9, 1] ] solve(N, edges, Q, query) # This code is contributed by Potta Lokesh |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Initial timer=1 static int timer = 1; // Simple DFS Function static void dfs(List<int> []adj, int []itime, int []otime, int src, int par) { // While visiting a node // mark its timer in time and // increase timer for next nodes itime[src] = timer++; foreach (int it in adj[src]) { if (it != par) { dfs(adj, itime, otime, it, src); } } // While leaving a node // mark its timer in out time // and increase timer for next nodes otime[src] = timer++; } // Check for subtree static bool check(int []itime, int []otime, int x, int y) { // Intime of y should be more // and outime should be less than x if (itime[x] < itime[y] && otime[x] > otime[y]) return true; return false; } // Function to solve the queries static void solve(int N, int[,] edges, int Q, int[,] query) { List<int> []adj = new List<int>[N + 1]; for (int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); // N-1 edges given for (int i = 0; i < N - 1; i++) { adj[edges[i,0]].Add(edges[i,1]); adj[edges[i,1]].Add(edges[i,0]); } // Array for intime int []intime = new int[N + 1]; // Array for outime int []outtime = new int[N + 1]; // Using DFS function // to find intime and outtime dfs(adj, intime, outtime, 1, -1); for (int i = 0; i < Q; i++) { int type = query[i,0], X = query[i,1], Y = query[i,2]; if (type == 0) { if (check(intime, outtime, X, Y)) { // To check if Y is present // in subtree of X Console.Write("Yes" +"\n"); } else { Console.Write("No" +"\n"); } } else { if (check(intime, outtime, Y, X)) { // To check if X is present // in subtree of Y Console.Write("Yes" +"\n"); } else { Console.Write("No" +"\n"); } } } } // Driver code public static void Main(String[] args) { int N = 9; // N is the number of nodes int[,] edges = { { 1, 2 }, { 1, 3 }, { 2, 6 }, { 2, 7 }, { 6, 9 }, { 7, 8 }, { 3, 4 }, { 3, 5 } }; int Q = 5; int[,] query = { { 0, 2, 8 }, { 1, 2, 8 }, { 1, 6, 5 }, { 0, 6, 5 }, { 1, 9, 1 } }; solve(N, edges, Q, query); }}// This code is contributed by Rajput-Ji |
Javascript
// JavaScript code for above approach// Initial timer=1let timer = 1;// Simple DFS Functionfunction dfs(adj, itime, otime, src, par) { // While visiting a node // mark its timer in time and // increase timer for next nodes itime[src] = timer++; for (let it of adj[src]) { if (it != par) { dfs(adj, itime, otime, it, src); } } // While leaving a node // mark its timer in out time // and increase timer for next nodes otime[src] = timer++;}// Check for subtreefunction check(itime, otime, x, y) { // Intime of y should be more // and outime should be less than x if (itime[x] < itime[y] && otime[x] > otime[y]) return true; return false;}// Function to solve the queriesfunction solve(N, edges, Q, query) { let adj = []; for (let i = 0; i <= N; i++) { adj[i] = []; } // N-1 edges given for (let i = 0; i < N - 1; i++) { adj[edges[i][0]].push(edges[i][1]); adj[edges[i][1]].push(edges[i][0]); } // Array for intime let intime = []; // Array for outime let outtime = []; // Using DFS function // to find intime and outtime dfs(adj, intime, outtime, 1, -1); for (let i = 0; i < Q; i++) { let type = query[i][0], X = query[i][1], Y = query[i][2]; if (type == 0) { if (check(intime, outtime, X, Y)) { // To check if Y is present // in subtree of X console.log("Yes"); } else { console.log("No"); } } else { if (check(intime, outtime, Y, X)) { // To check if X is present // in subtree of Y console.log("Yes"); } else { console.log("No"); } } }}// Driver codelet N = 9;// N is the number of nodeslet edges = [ [1, 2], [1, 3], [2, 6], [2, 7], [6, 9], [7, 8], [3, 4], [3, 5],];let Q = 5;let query = [ [0, 2, 8], [1, 2, 8], [1, 6, 5], [0, 6, 5], [1, 9, 1],];solve(N, edges, Q, query);// This code is contributed by adityamaharshi |
Output
Yes No No No Yes
Time Complexity: O(max (N, Q))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
