Posted on by Kalkicode
Code Tree

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

This article delves into the fascinating world of N-ary trees, where the goal is to uncover the Kth ancestor nodes within such a tree. Through a comprehensive breakdown of the problem, solution strategy, and code implementation, readers will discover how to navigate the intricacies of N-ary trees and identify these significant ancestor nodes.

## Problem Statement

Given an N-ary tree and a value K, the task is to find and display all nodes that are Kth ancestors of their respective descendants.

## Example

Consider the following N-ary tree:

``````
10
/   \
/     \
/       \
8         5
/|\      /|\ \
/ | \    / | \ \
-2 1  6  7 18 3  4
/ \           /| \
9  11         2 1  3
/  \
17   12
``````

For K = 2, the output is:

``````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]``````

## Solution Strategy

1. Create a class `TreeNode` to represent nodes in the N-ary tree. This class should contain a value and a vector of children.
2. Implement the `NAryTree` class, responsible for building the N-ary tree and finding Kth ancestor nodes.
3. Traverse the tree and maintain a path to the current node.
4. For each node, check if the path length is at least K + 1. If it is, display the Kth ancestor using the element at index (path_length - K - 1) of the path.
5. Recurse through the children of each node to explore the entire tree.

## Code Solution

``````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]``````

## Time Complexity Analysis

In the worst case, the traversal of the N-ary tree requires visiting each node once. Since the tree's depth is limited, the time complexity is O(n), where n is the number of nodes in the tree.

## 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.

Categories
Relative Post