Skip to main content

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 > ();
	}
	// 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]




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.

New Comment