Given a tree of N nodes and N-1 edges. Also given an integer M and a node, the task is to print the M-th node in the DFS of the subtree of a given node for multiple queries.
Note: M will not be greater than the number of nodes in the subtree of the given node.
Input: M = 3, node = 1
Output: 4
In the above example if 1 is given as the node, then the DFS of subtree will be 1 2 4 6 7 5 3, hence if M is 3, then the 3rd node is 4Input: M = 4, node = 2
Output: 7
If 2 is given as the node, then the DFS of the subtree will be 2 4 6 7 5., hence if M is 4 then the 4th node is 7.
Approach:
- Add the edges between the nodes in an adjacency list.
- Call DFS function to generate the DFS of the complete tree.
- Use an under[] array to store the height of the subtree under the given node including the node.
- In the DFS function, keep incrementing the size of subtree on every recursive call.
- Mark the node index in the DFS of complete using hashing.
- Let index of given node in the DFS of the tree be ind, then the M-th node will be at index ind + M -1 as the DFS of a subtree of a node will always be a contiguous subarray starting from the node.
Below is the implementation of the above approach.
C++
// C++ program for Queries// for DFS of subtree of a node in a tree#include <bits/stdc++.h>using namespace std;const int N = 100000;// Adjacency list to store the// tree nodes connectionvector<int> v[N];// stores the index of node in DFSunordered_map<int, int> mp;// stores the index of node in// original nodevector<int> a;// Function to call DFS and count nodes// under that subtreevoid dfs(int under[], int child, int parent){ // stores the DFS of tree a.push_back(child); // height of subtree under[child] = 1; // iterate for children for (auto it : v[child]) { // if not equal to parent // so that it does not traverse back if (it != parent) { // call DFS for subtree dfs(under, it, child); // add the height under[child] += under[it]; } }}// Function to return the DFS of subtree of nodeint printnodeDFSofSubtree(int node, int under[], int m){ // index of node in the original DFS int ind = mp[node]; // height of subtree of node return a[ind + m - 1];}// Function to add edges to a treevoid addEdge(int x, int y){ v[x].push_back(y); v[y].push_back(x);}// Marks the index of node in original DFSvoid markIndexDfs(){ int size = a.size(); // marks the index for (int i = 0; i < size; i++) { mp[a[i]] = i; }}// Driver Codeint main(){ int n = 7; // add edges of a tree addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // array to store the height of subtree // of every node in a tree int under[n + 1]; // Call the function DFS to generate the DFS dfs(under, 1, 0); // Function call to mark the index of node markIndexDfs(); int m = 3; // Query 1 cout << printnodeDFSofSubtree(1, under, m) << endl; // Query 2 m = 4; cout << printnodeDFSofSubtree(2, under, m); return 0;} |
Java
// Java program for Queries for// DFS of subtree of a node in a treeimport java.util.*;class GFG{ // Adjacency list to store the// tree nodes connectionstatic ArrayList<ArrayList<Integer>> v;// Stores the index of node in DFSstatic HashMap<Integer, Integer> mp;// Stores the index of node in// original nodestatic ArrayList<Integer> a;// Function to call DFS and count nodes// under that subtreestatic void dfs(int under[], int child, int parent){ // Stores the DFS of tree a.add(child); // Height of subtree under[child] = 1; // iterate for children for(int it : v.get(child)) { // If not equal to parent // so that it does not traverse back if (it != parent) { // Call DFS for subtree dfs(under, it, child); // Add the height under[child] += under[it]; } }}// Function to return the DFS of subtree of nodestatic int printnodeDFSofSubtree(int node, int under[], int m){ // Index of node in the original DFS int ind = mp.get(node); // Height of subtree of node return a.get(ind + m - 1);}// Function to add edges to a treestatic void addEdge(int x, int y){ v.get(x).add(y); v.get(y).add(x);}// Marks the index of node in original DFSstatic void markIndexDfs(){ int size = a.size(); // Marks the index for(int i = 0; i < size; i++) { mp.put(a.get(i), i); }}// Driver Codepublic static void main(String[] args){ int n = 7; mp = new HashMap<>(); v = new ArrayList<>(); a = new ArrayList<>(); for(int i = 0; i < n + 1; i++) v.add(new ArrayList<>()); // Add edges of a tree addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // Array to store the height of subtree // of every node in a tree int under[] = new int[n + 1]; // Call the function DFS to generate the DFS dfs(under, 1, 0); // Function call to mark the index of node markIndexDfs(); int m = 3; // Query 1 System.out.println( printnodeDFSofSubtree(1, under, m)); // Query 2 m = 4; System.out.println( printnodeDFSofSubtree(2, under, m));}}// This code is contributed by jrishabh99 |
Python3
# Python3 program for Queries # for DFS of subtree of a node in a tree N = 100000# Adjacency list to store the # tree nodes connection v = [[]for i in range(N)]# stores the index of node in DFS mp = {}# stores the index of node in # original node a = []# Function to call DFS and count nodes # under that subtree def dfs(under, child, parent): # stores the DFS of tree a.append(child) # height of subtree under[child] = 1 # iterate for children for it in v[child]: # if not equal to parent # so that it does not traverse back if (it != parent): # call DFS for subtree dfs(under, it, child) # add the height under[child] += under[it] # Function to return the DFS of subtree of node def printnodeDFSofSubtree(node, under, m): # index of node in the original DFS ind = mp[node] # height of subtree of node return a[ind + m - 1] # Function to add edges to a tree def addEdge(x, y): v[x].append(y) v[y].append(x) # Marks the index of node in original DFS def markIndexDfs(): size = len(a) # marks the index for i in range(size): mp[a[i]] = i # Driver Code n = 7# add edges of a tree addEdge(1, 2) addEdge(1, 3) addEdge(2, 4) addEdge(2, 5) addEdge(4, 6) addEdge(4, 7) # array to store the height of subtree # of every node in a tree under = [0]*(n + 1)# Call the function DFS to generate the DFS dfs(under, 1, 0) # Function call to mark the index of node markIndexDfs() m = 3# Query 1 print(printnodeDFSofSubtree(1, under, m))# Query 2 m = 4print(printnodeDFSofSubtree(2, under, m))# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program for Queries for DFS// of subtree of a node in a treeusing System;using System.Collections.Generic;class GFG{ // Adjacency list to store the// tree nodes connectionstatic List<List<int>> v;// Stores the index of node in DFSstatic Dictionary<int, int> mp;// Stores the index of node in// original nodestatic List<int> a;// Function to call DFS and count nodes// under that subtreestatic void dfs(int []under, int child, int parent){ // Stores the DFS of tree a.Add(child); // Height of subtree under[child] = 1; // Iterate for children foreach(int it in v[child]) { // If not equal to parent so // that it does not traverse back if (it != parent) { // Call DFS for subtree dfs(under, it, child); // Add the height under[child] += under[it]; } }}// Function to return the DFS of subtree of nodestatic int printnodeDFSofSubtree(int node, int []under, int m){ // Index of node in the original DFS int ind = mp[node]; // Height of subtree of node return a[ind + m - 1];}// Function to add edges to a treestatic void addEdge(int x, int y){ v[x].Add(y); v[y].Add(x);}// Marks the index of node in original DFSstatic void markIndexDfs(){ int size = a.Count; // Marks the index for(int i = 0; i < size; i++) { mp.Add(a[i], i); }}// Driver Codepublic static void Main(String[] args){ int n = 7; mp = new Dictionary<int, int>(); v = new List<List<int>>(); a = new List<int>(); for(int i = 0; i < n + 1; i++) v.Add(new List<int>()); // Add edges of a tree addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // Array to store the height of subtree // of every node in a tree int []under = new int[n + 1]; // Call the function DFS to generate the DFS dfs(under, 1, 0); // Function call to mark the index of node markIndexDfs(); int m = 3; // Query 1 Console.WriteLine( printnodeDFSofSubtree(1, under, m)); // Query 2 m = 4; Console.WriteLine( printnodeDFSofSubtree(2, under, m));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for Queries for DFS// of subtree of a node in a tree // Adjacency list to store the// tree nodes connectionvar v = [];// Stores the index of node in DFSvar mp = new Map();// Stores the index of node in// original nodevar a = [];// Function to call DFS and count nodes// under that subtreefunction dfs(under, child, parent){ // Stores the DFS of tree a.push(child); // Height of subtree under[child] = 1; // Iterate for children for(var it of v[child]) { // If not equal to parent so // that it does not traverse back if (it != parent) { // Call DFS for subtree dfs(under, it, child); // Push the height under[child] += under[it]; } }}// Function to return the DFS of subtree of nodefunction printnodeDFSofSubtree(node, under, m){ // Index of node in the original DFS var ind = mp.get(node); // Height of subtree of node return a[ind + m - 1];}// Function to add edges to a treefunction addEdge(x, y){ v[x].push(y); v[y].push(x);}// Marks the index of node in original DFSfunction markIndexDfs(){ var size = a.length; // Marks the index for(var i = 0; i < size; i++) { mp.set(a[i], i); }}// Driver Codevar n = 7;mp = new Map();v = [];a = [];for(var i = 0; i < n + 1; i++) v.push(Array()); // Push edges of a treeaddEdge(1, 2);addEdge(1, 3);addEdge(2, 4);addEdge(2, 5);addEdge(4, 6);addEdge(4, 7);// Array to store the height of subtree// of every node in a treevar under = new Array(n + 1);// Call the function DFS to generate the DFSdfs(under, 1, 0);// Function call to mark the index of nodemarkIndexDfs();var m = 3;// Query 1document.write(printnodeDFSofSubtree( 1, under, m) + "<br>"); // Query 2m = 4;document.write(printnodeDFSofSubtree( 2, under, m));// This code is contributed by rutvik_56</script> |
Output
4 7
Complexity Analysis:
- Time Complexity: O(1), for processing each query.
- 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!
