# Find the all Kth ancestor nodes in an N-ary tree

Here given code implementation process.

``````import java.util.Vector;
import java.util.ArrayList;
// Java program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
public int key;
public Vector < TreeNode > child;
public TreeNode(int key)
{
this.key = key;
this.child = new Vector < TreeNode > ();
}
{
TreeNode t = new TreeNode(key);
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
// Print every Kth ancestor in n-arr tree node
public void printKthAncestor(ArrayList < Integer > path,
TreeNode node, int k)
{
if (node == null)
{
return;
}
int i = 0;
// iterating the child of given node
while (i < node.child.size())
{
// Recursively visit child node
printKthAncestor(path, node.child.get(i), k);
i++;
}
int n = path.size();
if (n >= k + 1)
{
System.out.println(" Node [" + node.key + "] : Ancestor : [" +
path.get((n - k) - 1) + "] ");
}
else
{
// When kth ancestor not exist
System.out.println(" Node [" + node.key + "] : Ancestor : [None] ");
}
if (path.size() > 0)
{
path.remove(path.size() - 1);
}
}
public void everyKthAncestor(int k)
{
if (k <= 0)
{
return;
}
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
return;
}
// Use to collect tree path
ArrayList < Integer > path = new ArrayList < Integer > ();
// Display given k
System.out.println(" Given K [" + k + "]");
// Display Kth ancestor
printKthAncestor(path, this.root, k);
}
public static void main(String[] args)
{
NAryTree tree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}
}``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````// Include header file
#include <iostream>
#include <vector>
using namespace std;

// C++ program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
public: int key;
vector < TreeNode* > child;
TreeNode(int key)
{
this->key = key;
}
{
TreeNode *t = new TreeNode(key);
this->child.push_back(t);
}
};
class NAryTree
{
public: TreeNode *root;
NAryTree()
{
this->root = NULL;
}
// Print every Kth ancestor in n-arr tree node
void printKthAncestor(vector < int > path, TreeNode *node, int k)
{
if (node == NULL)
{
return;
}
int i = 0;
path.push_back(node->key);
// iterating the child of given node
while (i < node->child.size())
{
// Recursively visit child node
this->printKthAncestor(path, node->child.at(i), k);
i++;
}
int n = path.size();
if (n >= k + 1)
{
cout << " Node [" << node->key << "] : Ancestor : ["
<< path.at((n - k) - 1) << "] " << endl;
}
else
{
// When kth ancestor not exist
cout << " Node [" << node->key
<< "] : Ancestor : [None] " << endl;
}
if (n > 0)
{
path.pop_back();
}
}
void everyKthAncestor(int k)
{
if (k <= 0)
{
return;
}
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
return;
}
// Use to collect tree path
vector < int > path ;
// Display given k
cout << " Given K [" << k << "]" << endl;
// Display Kth ancestor
this->printKthAncestor(path, this->root, k);
}
};
int main()
{
NAryTree *tree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree->root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree->everyKthAncestor(2);
return 0;
}``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Find the all Kth ancestor nodes in an N-ary tree
public class TreeNode
{
public int key;
public List < TreeNode > child;
public TreeNode(int key)
{
this.key = key;
this.child = new List < TreeNode > ();
}
{
TreeNode t = new TreeNode(key);
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
// Print every Kth ancestor in n-arr tree node
public void printKthAncestor(List < int > path, TreeNode node, int k)
{
if (node == null)
{
return;
}
int i = 0;
// iterating the child of given node
while (i < node.child.Count)
{
// Recursively visit child node
this.printKthAncestor(path, node.child[i], k);
i++;
}
int n = path.Count;
if (n >= k + 1)
{
Console.WriteLine(" Node [" + node.key + "] : Ancestor : [" + path[(n - k) - 1] + "] ");
}
else
{
// When kth ancestor not exist
Console.WriteLine(" Node [" + node.key + "] : Ancestor : [None] ");
}
if (path.Count > 0)
{
path.RemoveAt(path.Count - 1);
}
}
public void everyKthAncestor(int k)
{
if (k <= 0)
{
return;
}
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
return;
}
// Use to collect tree path
List < int > path = new List < int > ();
// Display given k
Console.WriteLine(" Given K [" + k + "]");
// Display Kth ancestor
this.printKthAncestor(path, this.root, k);
}
public static void Main(String[] args)
{
NAryTree tree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}
}``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````<?php
// Php program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
public \$key;
public \$child;
public	function __construct(\$key)
{
\$this->key = \$key;
\$this->child = array();
}
{
\$t = new TreeNode(\$key);
\$this->child[] = \$t;
}
}
class NAryTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
// Print every Kth ancestor in n-arr tree node
public	function printKthAncestor(&\$path, \$node, \$k)
{
if (\$node == NULL)
{
return;
}
\$i = 0;
\$path[] = \$node->key;
// iterating the child of given node
while (\$i < count(\$node->child))
{
// Recursively visit child node
\$this->printKthAncestor(\$path, \$node->child[\$i], \$k);
\$i++;
}
\$n = count(\$path);
if (\$n >= \$k + 1)
{
echo(" Node [".\$node->key.
"] : Ancestor : [".\$path[(\$n - \$k) - 1].
"] ".
"\n");
}
else
{
// When kth ancestor not exist
echo(" Node [".\$node->key.
"] : Ancestor : [None] ".
"\n");
}
if (\$n > 0)
{
array_pop(\$path);
}
}
public	function everyKthAncestor(\$k)
{
if (\$k <= 0)
{
return;
}
if (\$this->root == NULL)
{
echo("\n Empty Tree \n");
return;
}
// Use to collect tree path
\$path = array();
// Display given k
echo(" Given K [".\$k.
"]".
"\n");
// Display Kth ancestor
\$this->printKthAncestor(\$path, \$this->root, \$k);
}
}

function main()
{
\$tree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
\$tree->root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
\$tree->everyKthAncestor(2);
}
main();``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````// Node JS program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
constructor(key)
{
this.key = key;
this.child = [];
}
{
var t = new TreeNode(key);
this.child.push(t);
}
}
class NAryTree
{
constructor()
{
this.root = null;
}
// Print every Kth ancestor in n-arr tree node
printKthAncestor(path, node, k)
{
if (node == null)
{
return;
}
var i = 0;
path.push(node.key);
// iterating the child of given node
while (i < node.child.length)
{
// Recursively visit child node
this.printKthAncestor(path, node.child[i], k);
i++;
}
var n = path.length;
if (n >= k + 1)
{
console.log(" Node [" + node.key + "] : Ancestor : [" + path[(n - k) - 1] + "] ");
}
else
{
// When kth ancestor not exist
console.log(" Node [" + node.key + "] : Ancestor : [None] ");
}
if (n > 0)
{
path.pop();
}
}
everyKthAncestor(k)
{
if (k <= 0)
{
return;
}
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
return;
}
// Use to collect tree path
var path = [];
// Display given k
console.log(" Given K [" + k + "]");
// Display Kth ancestor
this.printKthAncestor(path, this.root, k);
}
}

function main()
{
var tree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}
main();``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````#  Python 3 program for
#  Find the all Kth ancestor nodes in an N-ary tree
class TreeNode :
def __init__(self, key) :
self.key = key
self.child = []

t = TreeNode(key)
self.child.append(t)

class NAryTree :
def __init__(self) :
self.root = None

#  Print every Kth ancestor in n-arr tree node
def printKthAncestor(self, path, node, k) :
if (node == None) :
return

i = 0
path.append(node.key)
#  iterating the child of given node
while (i < len(node.child)) :
#  Recursively visit child node
self.printKthAncestor(path, node.child[i], k)
i += 1

n = len(path)
if (n >= k + 1) :
print(" Node [", node.key ,"] : Ancestor : [",
path[(n - k) - 1] ,"] ")
else :
#  When kth ancestor not exist
print(" Node [", node.key ,"] : Ancestor : [None] ")

if (n > 0) :
path.pop()

def everyKthAncestor(self, k) :
if (k <= 0) :
return

if (self.root == None) :
print("\n Empty Tree ")
return

#  Use to collect tree path
path = []
#  Display given k
print(" Given K [", k ,"]")
#  Display Kth ancestor
self.printKthAncestor(path, self.root, k)

def main() :
tree = NAryTree()
#           10
#          /   \
#         /     \
#        /       \
#       8         5
#      /|\      /|\ \
#     / | \    / | \ \
#    -2 1  6  7 18 3  4
#      / \           /| \
#     9  11         2 1  3
#       /  \
#      17   12
#    -----------------------
#    Constructing N-Arr tree

#  First element of tree
tree.root = TreeNode(10)
#  Add child node [-2,1,5] in node (8)
#  Add child node [9,11] in node (1)
#  Add child node [17  12] in node (11)
#  Add child node [7 18 3  4] in node (5)
#  Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2)

if __name__ == "__main__": main()``````

#### input

`````` Given K [ 2 ]
Node [ -2 ] : Ancestor : [ 10 ]
Node [ 9 ] : Ancestor : [ 8 ]
Node [ 17 ] : Ancestor : [ 1 ]
Node [ 12 ] : Ancestor : [ 1 ]
Node [ 11 ] : Ancestor : [ 8 ]
Node [ 1 ] : Ancestor : [ 10 ]
Node [ 6 ] : Ancestor : [ 10 ]
Node [ 8 ] : Ancestor : [None]
Node [ 7 ] : Ancestor : [ 10 ]
Node [ 18 ] : Ancestor : [ 10 ]
Node [ 3 ] : Ancestor : [ 10 ]
Node [ 2 ] : Ancestor : [ 5 ]
Node [ 1 ] : Ancestor : [ 5 ]
Node [ 3 ] : Ancestor : [ 5 ]
Node [ 4 ] : Ancestor : [ 10 ]
Node [ 5 ] : Ancestor : [None]
Node [ 10 ] : Ancestor : [None]``````
``````#  Ruby program for
#  Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :key, :child
def initialize(key)
self.key = key
self.child = []
end

t = TreeNode.new(key)
self.child.push(t)
end

end

class NAryTree
# Define the accessor and reader of class NAryTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Print every Kth ancestor in n-arr tree node
def printKthAncestor(path, node, k)
if (node == nil)
return
end

i = 0
path.push(node.key)
#  iterating the child of given node
while (i < node.child.length)
#  Recursively visit child node
self.printKthAncestor(path, node.child[i], k)
i += 1
end

n = path.length
if (n >= k + 1)
print(" Node [", node.key ,"] : Ancestor : [",
path[(n - k) - 1] ,"] ", "\n")
else
#  When kth ancestor not exist
print(" Node [", node.key ,"] : Ancestor : [None] ", "\n")
end

if (n > 0)
path.pop()
end

end

def everyKthAncestor(k)
if (k <= 0)
return
end

if (self.root == nil)
print("\n Empty Tree \n")
return
end

#  Use to collect tree path
path = []
#  Display given k
print(" Given K [", k ,"]", "\n")
#  Display Kth ancestor
self.printKthAncestor(path, self.root, k)
end

end

def main()
tree = NAryTree.new()
#           10
#          /   \
#         /     \
#        /       \
#       8         5
#      /|\      /|\ \
#     / | \    / | \ \
#    -2 1  6  7 18 3  4
#      / \           /| \
#     9  11         2 1  3
#       /  \
#      17   12
#    -----------------------
#    Constructing N-Arr tree

#  First element of tree
tree.root = TreeNode.new(10)
#  Add child node [-2,1,5] in node (8)
#  Add child node [9,11] in node (1)
#  Add child node [17  12] in node (11)
#  Add child node [7 18 3  4] in node (5)
#  Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2)
end

main()``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]
``````
``````import scala.collection.mutable._;
// Scala program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode(var key: Int , var child: ArrayBuffer[TreeNode])
{
def this(key: Int)
{
this(key,new ArrayBuffer[TreeNode]());
}
def addChild(key: Int): Unit = {
var t: TreeNode = new TreeNode(key);
this.child += t;
}
}
class NAryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Print every Kth ancestor in n-arr tree node
def printKthAncestor(path: ArrayBuffer[Int], node: TreeNode, k: Int): Unit = {
if (node == null)
{
return;
}
var i: Int = 0;
path += node.key;
// iterating the child of given node
while (i < node.child.size)
{
// Recursively visit child node
printKthAncestor(path, node.child(i), k);
i += 1;
}
var n: Int = path.size;
if (n >= k + 1)
{
println(" Node [" + node.key +
"] : Ancestor : [" + path((n - k) - 1) + "] ");
}
else
{
// When kth ancestor not exist
println(" Node [" + node.key + "] : Ancestor : [None] ");
}
if (n > 0)
{
path.remove(n - 1);
}
}
def everyKthAncestor(k: Int): Unit = {
if (k <= 0)
{
return;
}
if (this.root == null)
{
print("\n Empty Tree \n");
return;
}
// Use to collect tree path
var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
// Display given k
println(" Given K [" + k + "]");
// Display Kth ancestor
printKthAncestor(path, this.root, k);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: NAryTree = new NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}
}``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````
``````// Swift 4 program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
var key: Int;
var child: [TreeNode?] ;
init(_ key: Int)
{
self.key = key;
self.child = [TreeNode]();
}
{
let t: TreeNode = TreeNode(key);
self.child.append(t);
}
}
class NAryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Print every Kth ancestor in n-arr tree node
func printKthAncestor(_ path: inout[Int] , _ node : TreeNode? , _ k : Int)
{
if (node == nil)
{
return;
}
var i: Int = 0;
path.append(node!.key);
// iterating the child of given node
while (i < node!.child.count)
{
// Recursively visit child node
self.printKthAncestor(&path, node!.child[i], k);
i += 1;
}
let n: Int = path.count;
if (n >= k + 1)
{
print(" Node [", node!.key ,"] : Ancestor : [",
path[(n - k) - 1] ,"] ");
}
else
{
// When kth ancestor not exist
print(" Node [", node!.key ,"] : Ancestor : [None] ");
}
if (n > 0)
{
path.removeLast();
}
}
func everyKthAncestor(_ k: Int)
{
if (k <= 0)
{
return;
}
if (self.root == nil)
{
print("\n Empty Tree ");
return;
}
// Use to collect tree path
var path: [Int] = [Int]();
// Display given k
print(" Given K [", k ,"]");
// Display Kth ancestor
self.printKthAncestor(&path, self.root, k);
}
}
func main()
{
let tree: NAryTree = NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}
main();``````

#### input

`````` Given K [ 2 ]
Node [ -2 ] : Ancestor : [ 10 ]
Node [ 9 ] : Ancestor : [ 8 ]
Node [ 17 ] : Ancestor : [ 1 ]
Node [ 12 ] : Ancestor : [ 1 ]
Node [ 11 ] : Ancestor : [ 8 ]
Node [ 1 ] : Ancestor : [ 10 ]
Node [ 6 ] : Ancestor : [ 10 ]
Node [ 8 ] : Ancestor : [None]
Node [ 7 ] : Ancestor : [ 10 ]
Node [ 18 ] : Ancestor : [ 10 ]
Node [ 3 ] : Ancestor : [ 10 ]
Node [ 2 ] : Ancestor : [ 5 ]
Node [ 1 ] : Ancestor : [ 5 ]
Node [ 3 ] : Ancestor : [ 5 ]
Node [ 4 ] : Ancestor : [ 10 ]
Node [ 5 ] : Ancestor : [None]
Node [ 10 ] : Ancestor : [None]``````
``````// Kotlin program for
// Find the all Kth ancestor nodes in an N-ary tree
class TreeNode
{
var key: Int;
var child: MutableList<TreeNode> ;
constructor(key: Int)
{
this.key = key;
this.child = mutableListOf<TreeNode>();
}
{
val t: TreeNode = TreeNode(key);
}
}
class NAryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Print every Kth ancestor in n-arr tree node
fun printKthAncestor(path: MutableList<Int> , node : TreeNode ? , k : Int): Unit
{
if (node == null)
{
return;
}
var i: Int = 0;
// iterating the child of given node
while (i < node.child.size)
{
// Recursively visit child node
this.printKthAncestor(path, node.child[i], k);
i += 1;
}
val n: Int = path.size;
if (n >= k + 1)
{
println(" Node [" + node.key + "] : Ancestor : [" + path[(n - k) - 1] + "] ");
}
else
{
// When kth ancestor not exist
println(" Node [" + node.key + "] : Ancestor : [None] ");
}
if (n > 0)
{
path.removeAt(n - 1);
}
}
fun everyKthAncestor(k: Int): Unit
{
if (k <= 0)
{
return;
}
if (this.root == null)
{
print("\n Empty Tree \n");
return;
}
// Use to collect tree path
val path: MutableList<Int> = mutableListOf<Int>();
// Display given k
println(" Given K [" + k + "]");
// Display Kth ancestor
this.printKthAncestor(path, this.root, k);
}
}
fun main(args: Array < String > ): Unit
{
val tree: NAryTree = NAryTree();
/*
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
// Add child node [-2,1,5] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (7)
tree.everyKthAncestor(2);
}``````

#### input

`````` Given K [2]
Node [-2] : Ancestor : [10]
Node [9] : Ancestor : [8]
Node [17] : Ancestor : [1]
Node [12] : Ancestor : [1]
Node [11] : Ancestor : [8]
Node [1] : Ancestor : [10]
Node [6] : Ancestor : [10]
Node [8] : Ancestor : [None]
Node [7] : Ancestor : [10]
Node [18] : Ancestor : [10]
Node [3] : Ancestor : [10]
Node [2] : Ancestor : [5]
Node [1] : Ancestor : [5]
Node [3] : Ancestor : [5]
Node [4] : Ancestor : [10]
Node [5] : Ancestor : [None]
Node [10] : Ancestor : [None]``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.