Depth-first search of subtrees in a tree using C++

In this problem, we get a binary tree and we need to execute dfs from a specific node, where we assume the given node as the root and execute dfs from it.

In the above tree assume we need to execute DFS node F

In this tutorial we will apply some unorthodox methods in order to significantly reduce our time complexity, so we are also able to run this code under higher constraints.

Method - In this approach we don't take the naive approach i.e. we simply apply dfs to each node as it doesn't work for higher constraints , so we try to use some unorthodox methods to avoid getting TLE.

#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it&#39;s index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and     precalculation our nodesunder
    a.push_back(child); // storing the dfs of our tree
    // nodesunder of child subtree
    nodesunder[child] = 1;
    for (auto it : v[child]) { // performing normal dfs

        if (it != parent) { // as we the child can climb up to
        //it&#39;s parent so we are trying to avoid that as it will become a cycle
            dfs(nodesunder, it, child); // recursive call
            nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
        //by the number of nodes under it&#39;s children
        }
    }
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
    int ind = mape[node]; // index of our node in the dfs array
    cout << "The DFS of subtree " << node << ": ";
    // print the DFS of subtree
    for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
    //printing all the nodes under our given node
        cout << a[i] << " ";
    }
    cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
    v[x].push_back(y);
    v[y].push_back(x);
}
void mark(){ // marking each node with it&#39;s index in dfs array
    int size = a.size();
    // marks the index
    for (int i = 0; i < size; i++) {
       mape[a[i]] = i;
    }
}
int main(){
    int n = 7;
    // add edges of a tree
    addEdgetoGraph(1, 2);
    addEdgetoGraph(1, 3);
    addEdgetoGraph(2, 4);
    addEdgetoGraph(2, 5);
    addEdgetoGraph(4, 6);
    addEdgetoGraph(4, 7);
    // array to store the nodes present under of subtree
    // of every node in a tree
    int nodesunder[n + 1];
    dfs(nodesunder, 1, 0); // generating our nodesunder array
    mark(); // marking the indices in map
    // Query 1
    printDFS(2, nodesunder);
    // Query 2
    printDFS(4, nodesunder);
    return 0;
}

Output

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

Understanding the code

In this method, we precompute the order of dfs and store it in the vector, when we precompute the dfs, We also count the nodes that exist under each subtree starting from each node, and then we simply traverse from the starting index of the then node to the number of all nodes that exist in its subtree.

Conclusion

In this tutorial, we solved a problem to solve the following query: DFS of subtrees in a tree. We also learned a C program for this problem and a complete method to solve this problem (Normal).

We can write the same program in other languages ​​(such as C, java, python, etc.). Hope this article is helpful to you.

The above is the detailed content of Depth-first search of subtrees in a tree using C++. For more information, please follow other related articles on the PHP Chinese website!