Given an n-ary tree rooted at vertex 1. The tree has n vertices and n-1 edges. Each node has a value associated with it and tree is input in the form of adjacency list. The task is to find the number of special nodes in the tree. A node is special if the path from the root to the node consists of distinct value nodes.
Examples:Â
Â
Input: val[] = {1, 2, 3, 4, 5, 7, 2, 3}
1
/ \
2 3
/ \ \
4 5 7
/ \
2 3
Output: 7
All nodes except the leaf node 2 are special.
Input: val[] = {2, 1, 4, 3, 4, 8, 10, 2, 5, 1}
2
/ \
1 4
/ \ \ \
3 4 8 10
/ \ \
2 5 1
Output: 8
Leaf nodes 2 and 1 are not special.
Â
Approach: The idea is to perform dfs on given tree using adjacency list. While performing dfs insert values of nodes visited in a set. If value of current node is already present in the set then current node and all nodes in the subtree rooted at current node are not special. After traversing subtree rooted at current node erase the value of current node from set as this value or node does not lie on path from root to all other unvisited nodes.Â
Below is the implementation of the above approach:
Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// DFS function to traverse the tree and find// number of special nodesvoid dfs(int val[], int n, vector<int> adj[], int v,         unordered_set<int>& values, int& ans){Â
    // If value of current node is already    // present earlier in path then this    // node and all other nodes connected to    // it are not special    if (values.count(val[v]))        return;Â
    // Insert value of current node in    // set of values traversed    ans++;    values.insert(val[v]);Â
    // Call dfs on all adjacent nodes    for (auto ele : adj[v]) {        dfs(val, n, adj, ele, values, ans);    }Â
    // Erase value of current node as all paths    // passing through current node are traversed    values.erase(val[v]);}Â
// Driver codeint main(){Â Â Â Â int val[] = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };Â Â Â Â int n = sizeof(val) / sizeof(val[0]);Â
    vector<int> adj[n];Â
    adj[1].push_back(2);    adj[1].push_back(3);    adj[2].push_back(4);    adj[2].push_back(5);    adj[2].push_back(6);    adj[3].push_back(7);    adj[5].push_back(8);    adj[5].push_back(9);    adj[5].push_back(10);Â
    unordered_set<int> values;Â
    int ans = 0;Â
    dfs(val, n, adj, 1, values, ans);Â
    cout << ans;Â
    return 0;} |
Java
// Java implementation of the approachimport java.util.*;Â
class GFG{Â
static int ans;Â
// DFS function to traverse the tree and find// number of special nodesstatic void dfs(int val[], int n, Vector<Integer> adj[], int v,        HashSet<Integer> values){Â
    // If value of current node is already    // present earlier in path then this    // node and all other nodes connected to    // it are not special    if (values.contains(val[v]))        return;Â
    // Insert value of current node in    // set of values traversed    ans++;    values.add(val[v]);Â
    // Call dfs on all adjacent nodes    for (int ele : adj[v])    {        dfs(val, n, adj, ele, values);    }Â
    // Erase value of current node as all paths    // passing through current node are traversed    values.remove(val[v]);}Â
// Driver codepublic static void main(String[] args){Â Â Â Â int val[] = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };Â Â Â Â int n = val.length;Â
    Vector<Integer> []adj = new Vector[n];    for(int i = 0; i < n ; i++)     {        adj[i] = new Vector<Integer>();    }    adj[1].add(2);    adj[1].add(3);    adj[2].add(4);    adj[2].add(5);    adj[2].add(6);    adj[3].add(7);    adj[5].add(8);    adj[5].add(9);    adj[5].add(10);Â
    ans = 0;    dfs(val, n, adj, 1, new HashSet<Integer>());    System.out.print(ans);}}Â
// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach Â
# DFS function to traverse the tree # and find number of special nodes def dfs(val, n, adj, v, values): Â
    # If value of current node is already     # present earlier in path then this     # node and all other nodes connected    # to it are not special     if val[v] in values:         return         global ansÂ
    # Insert value of current node in     # set of values traversed     ans += 1    values.add(val[v]) Â
    # Call dfs on all adjacent nodes     for ele in adj[v]:         dfs(val, n, adj, ele, values) Â
    # Erase value of current node as all     # paths passing through current node     # are traversed     values.remove(val[v]) Â
# Driver code if __name__ == "__main__":Â
    val = [0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1]     n = len(val) Â
    adj = [[] for i in range(n)] Â
    adj[1].append(2)     adj[1].append(3)     adj[2].append(4)     adj[2].append(5)     adj[2].append(6)     adj[3].append(7)     adj[5].append(8)     adj[5].append(9)     adj[5].append(10) Â
    values = set()     ans = 0    dfs(val, n, adj, 1, values)     print(ans) Â
# This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;Â
class GFG{  static int ans;  // DFS function to traverse the tree and find// number of special nodesstatic void dfs(int []val, int n, List<int> []adj, int v,        HashSet<int> values){      // If value of current node is already    // present earlier in path then this    // node and all other nodes connected to    // it are not special    if (values.Contains(val[v]))        return;      // Insert value of current node in    // set of values traversed    ans++;    values.Add(val[v]);      // Call dfs on all adjacent nodes    foreach (int ele in adj[v])    {        dfs(val, n, adj, ele, values);    }      // Erase value of current node as all paths    // passing through current node are traversed    values.Remove(val[v]);}  // Driver codepublic static void Main(String[] args){    int []val = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };    int n = val.Length;      List<int> []adj = new List<int>[n];    for(int i = 0; i < n ; i++)     {        adj[i] = new List<int>();    }    adj[1].Add(2);    adj[1].Add(3);    adj[2].Add(4);    adj[2].Add(5);    adj[2].Add(6);    adj[3].Add(7);    adj[5].Add(8);    adj[5].Add(9);    adj[5].Add(10);      ans = 0;    dfs(val, n, adj, 1, new HashSet<int>());    Console.Write(ans);}}Â
// This code is contributed by Rajput-Ji |
Javascript
<script>Â
// JavaScript implementation of the approachÂ
    var ans;Â
    // DFS function to traverse the tree and find    // number of special nodes    function dfs(val , n, adj , v, values) {Â
        // If value of current node is already        // present earlier in path then this        // node and all other nodes connected to        // it are not special        if (values.has(val[v]))            return;Â
        // Insert value of current node in        // set of values traversed        ans++;        values.add(val[v]);Â
        // Call dfs on all adjacent nodes        adj[v].forEach(function(ele) {                dfs(val, n, adj, ele, values);        });Â
        // Erase value of current node as all paths        // passing through current node are traversed        values.delete(val[v]);    }Â
    // Driver code             var val = [ 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 ];        var n = val.length;Â
        var adj = [];        for (var i = 0; i < n; i++) {            adj[i] = [];        }        adj[1].push(2);        adj[1].push(3);        adj[2].push(4);        adj[2].push(5);        adj[2].push(6);        adj[3].push(7);        adj[5].push(8);        adj[5].push(9);        adj[5].push(10);Â
        ans = 0;        dfs(val, n, adj, 1, new Set());        document.write(ans);Â
// This code contributed by aashish1995 Â
</script> |
Output:Â
8
Â
Time Complexity: O(n)Â
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!
