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
- Create a class
TreeNode
to represent nodes in the N-ary tree. This class should contain a value and a vector of children. - Implement the
NAryTree
class, responsible for building the N-ary tree and finding Kth ancestor nodes. - Traverse the tree and maintain a path to the current node.
- 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.
- 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 > ();
}
// Add new child
public void addChild(int key)
{
TreeNode t = new TreeNode(key);
this.child.add(t);
}
}
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;
// Add path node
path.add(node.key);
// 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);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root.child.get(0).addChild(-2);
tree.root.child.get(0).addChild(1);
tree.root.child.get(0).addChild(6);
// Add child node [9,11] in node (1)
tree.root.child.get(0).child.get(1).addChild(9);
tree.root.child.get(0).child.get(1).addChild(11);
// Add child node [17 12] in node (11)
tree.root.child.get(0).child.get(1).child.get(1).addChild(17);
tree.root.child.get(0).child.get(1).child.get(1).addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child.get(1).addChild(7);
tree.root.child.get(1).addChild(18);
tree.root.child.get(1).addChild(3);
tree.root.child.get(1).addChild(4);
// Add child node [2,1,3] in node (7)
tree.root.child.get(1).child.get(3).addChild(2);
tree.root.child.get(1).child.get(3).addChild(1);
tree.root.child.get(1).child.get(3).addChild(3);
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;
}
// Add new child
void addChild(int 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;
// Add path node
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);
tree->root->addChild(8);
tree->root->addChild(5);
// Add child node [-2,1,5] in node (8)
tree->root->child.at(0)->addChild(-2);
tree->root->child.at(0)->addChild(1);
tree->root->child.at(0)->addChild(6);
// Add child node [9,11] in node (1)
tree->root->child.at(0)->child.at(1)->addChild(9);
tree->root->child.at(0)->child.at(1)->addChild(11);
// Add child node [17 12] in node (11)
tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(17);
tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(12);
// Add child node [7 18 3 4] in node (5)
tree->root->child.at(1)->addChild(7);
tree->root->child.at(1)->addChild(18);
tree->root->child.at(1)->addChild(3);
tree->root->child.at(1)->addChild(4);
// Add child node [2,1,3] in node (7)
tree->root->child.at(1)->child.at(3)->addChild(2);
tree->root->child.at(1)->child.at(3)->addChild(1);
tree->root->child.at(1)->child.at(3)->addChild(3);
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 > ();
}
// Add new child
public void addChild(int key)
{
TreeNode t = new TreeNode(key);
this.child.Add(t);
}
}
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;
// Add path node
path.Add(node.key);
// 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);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root.child[0].addChild(-2);
tree.root.child[0].addChild(1);
tree.root.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9);
tree.root.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17);
tree.root.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7);
tree.root.child[1].addChild(18);
tree.root.child[1].addChild(3);
tree.root.child[1].addChild(4);
// Add child node [2,1,3] in node (7)
tree.root.child[1].child[3].addChild(2);
tree.root.child[1].child[3].addChild(1);
tree.root.child[1].child[3].addChild(3);
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();
}
// Add new child
public function addChild($key)
{
$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;
// Add path node
$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);
$tree->root->addChild(8);
$tree->root->addChild(5);
// Add child node [-2,1,5] in node (8)
$tree->root->child[0]->addChild(-2);
$tree->root->child[0]->addChild(1);
$tree->root->child[0]->addChild(6);
// Add child node [9,11] in node (1)
$tree->root->child[0]->child[1]->addChild(9);
$tree->root->child[0]->child[1]->addChild(11);
// Add child node [17 12] in node (11)
$tree->root->child[0]->child[1]->child[1]->addChild(17);
$tree->root->child[0]->child[1]->child[1]->addChild(12);
// Add child node [7 18 3 4] in node (5)
$tree->root->child[1]->addChild(7);
$tree->root->child[1]->addChild(18);
$tree->root->child[1]->addChild(3);
$tree->root->child[1]->addChild(4);
// Add child node [2,1,3] in node (7)
$tree->root->child[1]->child[3]->addChild(2);
$tree->root->child[1]->child[3]->addChild(1);
$tree->root->child[1]->child[3]->addChild(3);
$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 = [];
}
// Add new child
addChild(key)
{
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;
// Add path node
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);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root.child[0].addChild(-2);
tree.root.child[0].addChild(1);
tree.root.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9);
tree.root.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17);
tree.root.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7);
tree.root.child[1].addChild(18);
tree.root.child[1].addChild(3);
tree.root.child[1].addChild(4);
// Add child node [2,1,3] in node (7)
tree.root.child[1].child[3].addChild(2);
tree.root.child[1].child[3].addChild(1);
tree.root.child[1].child[3].addChild(3);
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 = []
# Add new child
def addChild(self, key) :
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
# Add path node
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)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,5] in node (8)
tree.root.child[0].addChild(-2)
tree.root.child[0].addChild(1)
tree.root.child[0].addChild(6)
# Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9)
tree.root.child[0].child[1].addChild(11)
# Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17)
tree.root.child[0].child[1].child[1].addChild(12)
# Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7)
tree.root.child[1].addChild(18)
tree.root.child[1].addChild(3)
tree.root.child[1].addChild(4)
# Add child node [2,1,3] in node (7)
tree.root.child[1].child[3].addChild(2)
tree.root.child[1].child[3].addChild(1)
tree.root.child[1].child[3].addChild(3)
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_reader :key, :child
attr_accessor :key, :child
def initialize(key)
self.key = key
self.child = []
end
# Add new child
def addChild(key)
t = TreeNode.new(key)
self.child.push(t)
end
end
class NAryTree
# Define the accessor and reader of class NAryTree
attr_reader :root
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
# Add path node
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)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,5] in node (8)
tree.root.child[0].addChild(-2)
tree.root.child[0].addChild(1)
tree.root.child[0].addChild(6)
# Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9)
tree.root.child[0].child[1].addChild(11)
# Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17)
tree.root.child[0].child[1].child[1].addChild(12)
# Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7)
tree.root.child[1].addChild(18)
tree.root.child[1].addChild(3)
tree.root.child[1].addChild(4)
# Add child node [2,1,3] in node (7)
tree.root.child[1].child[3].addChild(2)
tree.root.child[1].child[3].addChild(1)
tree.root.child[1].child[3].addChild(3)
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]());
}
// Add new child
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;
// Add path node
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);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root.child(0).addChild(-2);
tree.root.child(0).addChild(1);
tree.root.child(0).addChild(6);
// Add child node [9,11] in node (1)
tree.root.child(0).child(1).addChild(9);
tree.root.child(0).child(1).addChild(11);
// Add child node [17 12] in node (11)
tree.root.child(0).child(1).child(1).addChild(17);
tree.root.child(0).child(1).child(1).addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child(1).addChild(7);
tree.root.child(1).addChild(18);
tree.root.child(1).addChild(3);
tree.root.child(1).addChild(4);
// Add child node [2,1,3] in node (7)
tree.root.child(1).child(3).addChild(2);
tree.root.child(1).child(3).addChild(1);
tree.root.child(1).child(3).addChild(3);
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]();
}
// Add new child
func addChild(_ key: Int)
{
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;
// Add path node
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);
tree.root!.addChild(8);
tree.root!.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root!.child[0]!.addChild(-2);
tree.root!.child[0]!.addChild(1);
tree.root!.child[0]!.addChild(6);
// Add child node [9,11] in node (1)
tree.root!.child[0]!.child[1]!.addChild(9);
tree.root!.child[0]!.child[1]!.addChild(11);
// Add child node [17 12] in node (11)
tree.root!.child[0]!.child[1]!.child[1]!.addChild(17);
tree.root!.child[0]!.child[1]!.child[1]!.addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root!.child[1]!.addChild(7);
tree.root!.child[1]!.addChild(18);
tree.root!.child[1]!.addChild(3);
tree.root!.child[1]!.addChild(4);
// Add child node [2,1,3] in node (7)
tree.root!.child[1]!.child[3]!.addChild(2);
tree.root!.child[1]!.child[3]!.addChild(1);
tree.root!.child[1]!.child[3]!.addChild(3);
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>();
}
// Add new child
fun addChild(key: Int): Unit
{
val t: TreeNode = TreeNode(key);
this.child.add(t);
}
}
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;
// Add path node
path.add(node.key);
// 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);
tree.root?.addChild(8);
tree.root?.addChild(5);
// Add child node [-2,1,5] in node (8)
tree.root!!.child[0].addChild(-2);
tree.root!!.child[0].addChild(1);
tree.root!!.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root!!.child[0].child[1].addChild(9);
tree.root!!.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root!!.child[0].child[1].child[1].addChild(17);
tree.root!!.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root!!.child[1].addChild(7);
tree.root!!.child[1].addChild(18);
tree.root!!.child[1].addChild(3);
tree.root!!.child[1].addChild(4);
// Add child node [2,1,3] in node (7)
tree.root!!.child[1].child[3].addChild(2);
tree.root!!.child[1].child[3].addChild(1);
tree.root!!.child[1].child[3].addChild(3);
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.
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.
New Comment