Kth ancestor of all nodes in an N-ary tree using DFS
Given an N-ary tree and an integer K, the task is to print the Kth ancestors of all the nodes of the tree in level order manner. If K ancestors does not exist for a node, then print -1 for that node.
Examples:
Input: K = 2
Output: -1 -1 -1 1 1 1 1 1 1
Explanation:
2nd ancestor does not exist for nodes 1, 2 and 3
2nd ancestor of nodes 4, 5, 6, 7, 8, 9 is 1.Input: K = 1
Output: -1 1 1 2 2 2 3 3 3
Approach: The approach is to use DFS to find the ancestors of all the nodes. Below are the steps:
- The Kth parent of any node can be found by using DFS, and storing all parents of a node in a temporary vector say temp[].
- Whenever a node is visited in DFS, it is pushed in the temp vector.
- At the end of DFS, the currently visited node is popped from the temp vector.
- For the currently visited node, the vector contains all the ancestors of the node.
- The Kth node from the end of the vector is the Kth ancestor of the currently visited node, so store it in a ancestor[] array.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to add an// edge in the treevoid addEdge(vector<int> v[], int x, int y){ v[x].push_back(y); v[y].push_back(x);}// DFS to find the Kth// ancestor of every nodevoid dfs(vector<int> tree[], vector<int>& temp, int ancestor[], int u, int parent, int k){ // Pushing current node // in the vector temp.push_back(u); // Traverse its neighbors for (auto i : tree[u]) { if (i == parent) continue; dfs(tree, temp, ancestor, i, u, k); } temp.pop_back(); // If K ancestors are not // found for current node if (temp.size() < k) { ancestor[u] = -1; } else { // Add the Kth ancestor // for the node ancestor[u] = temp[temp.size() - k]; }}// Function to find Kth// ancestor of each nodevoid KthAncestor(int N, int K, int E, int edges[][2]){ // Building the tree vector<int> tree[N + 1]; for (int i = 0; i < E; i++) { addEdge(tree, edges[i][0], edges[i][1]); } // Stores all parents of a node vector<int> temp; // Store Kth ancestor // of all nodes int ancestor[N + 1]; dfs(tree, temp, ancestor, 1, 0, K); // Print the ancestors for (int i = 1; i <= N; i++) { cout << ancestor[i] << " "; }}int main(){ // Given N and K int N = 9; int K = 2; // Given edges of n-ary tree int E = 8; int edges[8][2] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 7 }, { 3, 8 }, { 3, 9 } }; // Function Call KthAncestor(N, K, E, edges); return 0;} |
Java
// Java implementation of// the above approachimport java.util.*;class GFG{// Function to add an// edge in the treestatic void addEdge(Vector<Integer> v[], int x, int y){ v[x].add(y); v[y].add(x);}// DFS to find the Kth// ancestor of every nodestatic void dfs(Vector<Integer> tree[], Vector<Integer> temp, int ancestor[], int u, int parent, int k){ // Pushing current node // in the vector temp.add(u); // Traverse its neighbors for(int i : tree[u]) { if (i == parent) continue; dfs(tree, temp, ancestor, i, u, k); } temp.remove(temp.size() - 1); // If K ancestors are not // found for current node if (temp.size() < k) { ancestor[u] = -1; } else { // Add the Kth ancestor // for the node ancestor[u] = temp.get(temp.size() - k); }}// Function to find Kth// ancestor of each nodestatic void KthAncestor(int N, int K, int E, int edges[][]){ // Building the tree @SuppressWarnings("unchecked") Vector<Integer> []tree = new Vector[N + 1]; for(int i = 0; i < tree.length; i++) tree[i] = new Vector<Integer>(); for(int i = 0; i < E; i++) { addEdge(tree, edges[i][0], edges[i][1]); } // Stores all parents of a node Vector<Integer> temp = new Vector<Integer>(); // Store Kth ancestor // of all nodes int []ancestor = new int[N + 1]; dfs(tree, temp, ancestor, 1, 0, K); // Print the ancestors for(int i = 1; i <= N; i++) { System.out.print(ancestor[i] + " "); }}// Driver codepublic static void main(String[] args){ // Given N and K int N = 9; int K = 2; // Given edges of n-ary tree int E = 8; int edges[][] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 7 }, { 3, 8 }, { 3, 9 } }; // Function call KthAncestor(N, K, E, edges);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 implementation of# the above approach# Function to add an# edge in the treedef addEdge(v, x, y): v[x].append(y) v[y].append(x)# DFS to find the Kth# ancestor of every nodedef dfs(tree, temp, ancestor, u, parent, k): # Pushing current node # in the vector temp.append(u) # Traverse its neighbors for i in tree[u]: if (i == parent): continue dfs(tree, temp, ancestor, i, u, k) temp.pop() # If K ancestors are not # found for current node if (len(temp) < k): ancestor[u] = -1 else: # Add the Kth ancestor # for the node ancestor[u] = temp[len(temp) - k]# Function to find Kth# ancestor of each nodedef KthAncestor(N, K, E, edges): # Building the tree tree = [[] for i in range(N + 1)] for i in range(E): addEdge(tree, edges[i][0], edges[i][1]) # Stores all parents of a node temp = [] # Store Kth ancestor # of all nodes ancestor = [0] * (N + 1) dfs(tree, temp, ancestor, 1, 0, K) # Print the ancestors for i in range(1, N + 1): print(ancestor[i], end = " ")# Driver codeif __name__ == '__main__': # Given N and K N = 9 K = 2 # Given edges of n-ary tree E = 8 edges = [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 7 ], [ 3, 8 ], [ 3, 9 ] ] # Function call KthAncestor(N, K, E, edges)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of// the above approachusing System;using System.Collections.Generic;class GFG{// Function to add an// edge in the treestatic void addEdge(List<int> []v, int x, int y){ v[x].Add(y); v[y].Add(x);}// DFS to find the Kth// ancestor of every nodestatic void dfs(List<int> []tree, List<int> temp, int []ancestor, int u, int parent, int k){ // Pushing current node // in the vector temp.Add(u); // Traverse its neighbors foreach(int i in tree[u]) { if (i == parent) continue; dfs(tree, temp, ancestor, i, u, k); } temp.RemoveAt(temp.Count - 1); // If K ancestors are not // found for current node if (temp.Count < k) { ancestor[u] = -1; } else { // Add the Kth ancestor // for the node ancestor[u] = temp[temp.Count - k]; }}// Function to find Kth// ancestor of each nodestatic void KthAncestor(int N, int K, int E, int [,]edges){ // Building the tree List<int> []tree = new List<int>[N + 1]; for(int i = 0; i < tree.Length; i++) tree[i] = new List<int>(); for(int i = 0; i < E; i++) { addEdge(tree, edges[i, 0], edges[i, 1]); } // Stores all parents of a node List<int> temp = new List<int>(); // Store Kth ancestor // of all nodes int []ancestor = new int[N + 1]; dfs(tree, temp, ancestor, 1, 0, K); // Print the ancestors for(int i = 1; i <= N; i++) { Console.Write(ancestor[i] + " "); }}// Driver codepublic static void Main(String[] args){ // Given N and K int N = 9; int K = 2; // Given edges of n-ary tree int E = 8; int [,]edges = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 7 }, { 3, 8 }, { 3, 9 } }; // Function call KthAncestor(N, K, E, edges);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function to add an // edge in the tree function addEdge(v, x, y) { v[x].push(y); v[y].push(x); } // DFS to find the Kth // ancestor of every node function dfs(tree, temp, ancestor, u, parent, k) { // Pushing current node // in the vector temp.push(u); // Traverse its neighbors for(let i = 0; i < tree[u].length; i++) { if (tree[u][i] == parent) continue; dfs(tree, temp, ancestor, tree[u][i], u, k); } temp.pop(); // If K ancestors are not // found for current node if (temp.length < k) { ancestor[u] = -1; } else { // Add the Kth ancestor // for the node ancestor[u] = temp[temp.length - k]; } } // Function to find Kth // ancestor of each node function KthAncestor(N, K, E, edges) { // Building the tree let tree = new Array(N + 1); for(let i = 0; i < tree.length; i++) tree[i] = []; for(let i = 0; i < E; i++) { addEdge(tree, edges[i][0], edges[i][1]); } // Stores all parents of a node let temp = []; // Store Kth ancestor // of all nodes let ancestor = new Array(N + 1); dfs(tree, temp, ancestor, 1, 0, K); // Print the ancestors for(let i = 1; i <= N; i++) { document.write(ancestor[i] + " "); } } // Given N and K let N = 9; let K = 2; // Given edges of n-ary tree let E = 8; let edges = [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 7 ], [ 3, 8 ], [ 3, 9 ] ]; // Function call KthAncestor(N, K, E, edges); </script> |
Output:
-1 -1 -1 1 1 1 1 1 1
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
