Given a tree of N nodes and N-1 edges. The task is to print the DFS of the subtree of a given node for multiple queries. The DFS must include the given node as the root of the subtree.
In the above tree, if 1 is given as the node, then the DFS of subtree will be 1 2 4 6 7 5 3.
If 2 is given as the node, then the DFS of the subtree will be 2 4 6 7 5..
Approach:
- Add the edges between the nodes in an adjacency list.
- Call DFS function to generate the DFS of the complete tree.
- Use a 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.
- The DFS of a subtree of a node will always be a contiguous subarray starting from the node(say index ind) to (ind+height of subtree).
- Get the index of node which has been stored using hashing and print the nodes from original DFS till index = ind + height of subtree which has been stored in under[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 print the DFS of subtree of nodevoid printDFSofSubtree(int node, int under[]){ // index of node in the original DFS int ind = mp[node]; // height of subtree of node int height = under[node]; cout << "The DFS of subtree " << node << ": "; // print the DFS of subtree for (int i = ind; i < ind + under[node]; i++) { cout << a[i] << " "; } cout << endl;}// 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(); // Query 1 printDFSofSubtree(2, under); // Query 1 printDFSofSubtree(4, under); return 0;} |
Java
// Java program for queries for DFS// of subtree of a node in a treeimport java.util.*;class GFG{ static int N = 100000;// Adjacency list to store the// tree nodes connection@SuppressWarnings("unchecked")static Vector<Integer> []v = new Vector[N];// Stores the index of node in DFSstatic HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();// Stores the index of node in// original nodestatic Vector<Integer> a = new Vector<>();// 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[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 print the DFS of subtree of nodestatic void printDFSofSubtree(int node, int under[]){ // Index of node in the original DFS int ind = mp.get(node); // Height of subtree of node int height = under[node]; System.out.print("The DFS of subtree " + node + ": "); // Print the DFS of subtree for(int i = ind; i < ind + under[node]; i++) { System.out.print(a.get(i) + " "); } System.out.println();}// 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.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; for(int i = 0; i < v.length; i++) v[i] = new Vector<Integer>(); // 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(); // Query 1 printDFSofSubtree(2, under); // Query 1 printDFSofSubtree(4, under);}}// This code is contributed by Amit Katiyar |
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 printDFSofSubtree(node, under): # index of node in the original DFS ind = mp[node] # height of subtree of node height = under[node] print("The DFS of subtree", node, ":", end=" ") # print the DFS of subtree for i in range(ind,ind + under[node]): print(a[i], end=" ") print() # 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() # Query 1 printDFSofSubtree(2, under)# Query 2 printDFSofSubtree(4, under)# 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{ static int N = 100000;// Adjacency list to // store the tree nodes // connectionstatic List<int> []v = new List<int>[N];// Stores the index of node in DFSstatic Dictionary<int, int> mp = new Dictionary<int, int>();// Stores the index of node in// original nodestatic List<int> a = new List<int>();// 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 print the DFS of // subtree of nodestatic void printDFSofSubtree(int node, int []under){ // Index of node in the // original DFS int ind = mp[node]; // Height of subtree of node int height = under[node]; Console.Write("The DFS of subtree " + node + ": "); // Print the DFS of subtree for(int i = ind; i < ind + under[node]; i++) { Console.Write(a[i] + " "); } Console.WriteLine();}// 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; for(int i = 0; i < v.Length; i++) v[i] = 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(); // Query 1 printDFSofSubtree(2, under); // Query 1 printDFSofSubtree(4, under);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for queries for DFS// of subtree of a node in a treevar N = 100000;// Adjacency list to // store the tree nodes // connectionvar v = Array.from(Array(N), () => Array());// 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 print the DFS of // subtree of nodefunction printDFSofSubtree(node, under){ // Index of node in the // original DFS var ind = mp.get(node); // Height of subtree of node var height = under[node]; document.write("The DFS of subtree " + node + ": "); // Print the DFS of subtree for(var i = ind; i < ind + under[node]; i++) { document.write(a[i] + " "); } document.write("<br>");}// 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;for(var i = 0; i < v.length; i++) v[i] = 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 = Array(n + 1);// Call the function DFS to// generate the DFSdfs(under, 1, 0);// Function call to mark the// index of nodemarkIndexDfs();// Query 1printDFSofSubtree(2, under);// Query 1printDFSofSubtree(4, under);// This code is contributed by rutvik_56</script> |
Output:
The DFS of subtree 2: 2 4 6 7 5 The DFS of subtree 4: 4 6 7
Time Complexity: O( N + M ), where N is the number of nodes and M is the number of edges for pre-calculation, and O(N) for queries in the worst case.
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!
