Skip to main content

Find height of n-ary tree

Delve into the world of N-ary trees as this article takes you on a journey to uncover the height of these intricate data structures. With a comprehensive breakdown of the problem, solution strategy, and practical Java code implementation, readers will gain a profound understanding of how to determine the height of N-ary trees.

Problem Statement

Given an N-ary tree, the task is to find and display its height.

Example

Consider the following N-ary tree:


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

The output is:

Height: 6

Solution Strategy

  1. Create a class TreeNode to represent nodes in the N-ary tree. This class should include a value and a vector of children.
  2. Implement the NAryTree class, responsible for building the N-ary tree, computing its height, and displaying the result.
  3. Utilize a recursive approach to traverse the tree and find the maximum height of subtrees.

Code Solution

import java.util.Vector;
import java.util.ArrayList;
// Java program for
// Find height of n-ary tree
class TreeNode
{
    public int key;
    public Vector < TreeNode > child;
    public TreeNode(int key)
    {
        this.key = key;
        this.child = new Vector < TreeNode > ();
    }
    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;
    }
    // Returns a maximum value of two numbers
    public int max(int a, int b)
    {
        if(a > b)
        {
            return a;
        }
        else
        {
            return b;
        }
    }
    public int findHeight(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        
        int i = 0;
        int height = 0;
        
        // iterating the child of given node
        while (i < node.child.size())
        {
            // Recursively visit child node
            height = max(findHeight(node.child.get(i)),height);
            i++;
        }
        // return new height
        return height+1;
    }
    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      20
                           |
                          -6 
            -----------------------
            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 (4)
        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);

        // Add child node [20] in node (2)
        tree.root.child.get(1).child.get(3).child.get(0).addChild(20);
        // Add child node [-6] in node (20)
        tree.root.child.get(1).child.get(3).child.get(0)
          .child.get(0).addChild(-6);
        
        // Get tree height
        int height = tree.findHeight(tree.root);

        // Display the calculated height
        System.out.print(" Height : "+height);
    }
}

input

 Height : 6
// Include header file
#include <iostream>
#include <vector>
using namespace std;

// C++ program for
// Find height of n-ary tree

class TreeNode
{
	public: int key;
	vector < TreeNode *> child;
	TreeNode(int key)
	{
		this->key = key;
	}
	void addChild(int key)
	{
		TreeNode *t = new TreeNode(key);
		this->child.push_back(t);
	}
};
class NAryTree
{
	public: TreeNode *root;
	NAryTree()
	{
		this->root = NULL;
	}
	// Returns a maximum value of two numbers
	int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	int findHeight(TreeNode *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		int i = 0;
		int height = 0;
		// iterating the child of given node
		while (i < node->child.size())
		{
			// Recursively visit child node
			height = this->max(this->findHeight(node->child.at(i)), height);
			i++;
		}
		// return new height
		return height + 1;
	}
};
int main()
{
	NAryTree *tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	                   |
	                  -6 
	    -----------------------
	    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 (4)
	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);
	// Add child node [20] in node (2)
	tree->root->child.at(1)->child.at(3)->child.at(0)->addChild(20);
	// Add child node [-6] in node (20)
	tree->root->child.at(1)->child.at(3)->child.at(0)
      ->child.at(0)->addChild(-6);
	// Get tree height
	int height = tree->findHeight(tree->root);
	// Display the calculated height
	cout << " Height : " << height;
	return 0;
}

input

 Height : 6
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Find height of 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 > ();
	}
	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;
	}
	// Returns a maximum value of two numbers
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	public int findHeight(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		int i = 0;
		int height = 0;
		// iterating the child of given node
		while (i < node.child.Count)
		{
			// Recursively visit child node
			height = this.max(this.findHeight(node.child[i]), height);
			i++;
		}
		// return new height
		return height + 1;
	}
	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      20
		                   |
		                  -6 
		    -----------------------
		    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 (4)
		tree.root.child[1].child[3].addChild(2);
		tree.root.child[1].child[3].addChild(1);
		tree.root.child[1].child[3].addChild(3);
		// Add child node [20] in node (2)
		tree.root.child[1].child[3].child[0].addChild(20);
		// Add child node [-6] in node (20)
		tree.root.child[1].child[3].child[0].child[0].addChild(-6);
		// Get tree height
		int height = tree.findHeight(tree.root);
		// Display the calculated height
		Console.Write(" Height : " + height);
	}
}

input

 Height : 6
<?php
// Php program for
// Find height of n-ary tree
class TreeNode
{
	public $key;
	public $child;
	public	function __construct($key)
	{
		$this->key = $key;
		$this->child = array();
	}
	public	function addChild($key)
	{
		$t = new TreeNode($key);
		$this->child[] = $t;
	}
}
class NAryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Returns a maximum value of two numbers
	public	function max($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	public	function findHeight($node)
	{
		if ($node == NULL)
		{
			return 0;
		}
		$i = 0;
		$height = 0;
		// iterating the child of given node
		while ($i < count($node->child))
		{
			// Recursively visit child node
			$height = $this->max($this->findHeight($node->child[$i]), $height);
			$i++;
		}
		// return new height
		return $height + 1;
	}
}

function main()
{
	$tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	                   |
	                  -6 
	    -----------------------
	    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 (4)
	$tree->root->child[1]->child[3]->addChild(2);
	$tree->root->child[1]->child[3]->addChild(1);
	$tree->root->child[1]->child[3]->addChild(3);
	// Add child node [20] in node (2)
	$tree->root->child[1]->child[3]->child[0]->addChild(20);
	// Add child node [-6] in node (20)
	$tree->root->child[1]->child[3]->child[0]->child[0]->addChild(-6);
	// Get tree height
	$height = $tree->findHeight($tree->root);
	// Display the calculated height
	echo(" Height : ".$height);
}
main();

input

 Height : 6
// Node JS program for
// Find height of n-ary tree
class TreeNode
{
	constructor(key)
	{
		this.key = key;
		this.child = [];
	}
	addChild(key)
	{
		var t = new TreeNode(key);
		this.child.push(t);
	}
}
class NAryTree
{
	constructor()
	{
		this.root = null;
	}
	// Returns a maximum value of two numbers
	max(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	findHeight(node)
	{
		if (node == null)
		{
			return 0;
		}
		var i = 0;
		var height = 0;
		// iterating the child of given node
		while (i < node.child.length)
		{
			// Recursively visit child node
			height = this.max(this.findHeight(node.child[i]), height);
			i++;
		}
		// return new height
		return height + 1;
	}
}

function main()
{
	var tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	                   |
	                  -6 
	    -----------------------
	    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 (4)
	tree.root.child[1].child[3].addChild(2);
	tree.root.child[1].child[3].addChild(1);
	tree.root.child[1].child[3].addChild(3);
	// Add child node [20] in node (2)
	tree.root.child[1].child[3].child[0].addChild(20);
	// Add child node [-6] in node (20)
	tree.root.child[1].child[3].child[0].child[0].addChild(-6);
	// Get tree height
	var height = tree.findHeight(tree.root);
	// Display the calculated height
	process.stdout.write(" Height : " + height);
}
main();

input

 Height : 6
#  Python 3 program for
#  Find height of n-ary tree
class TreeNode :
	def __init__(self, key) :
		self.key = key
		self.child = []
	
	def addChild(self, key) :
		t = TreeNode(key)
		self.child.append(t)
	

class NAryTree :
	def __init__(self) :
		self.root = None
	
	#  Returns a maximum value of two numbers
	def max(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	def findHeight(self, node) :
		if (node == None) :
			return 0
		
		i = 0
		height = 0
		#  iterating the child of given node
		while (i < len(node.child)) :
			#  Recursively visit child node
			height = self.max(self.findHeight(node.child[i]), height)
			i += 1
		
		#  return new height
		return height + 1
	

def main() :
	tree = NAryTree()
	#           10
	#          /   \
	#         /     \
	#        /       \   
	#       8         5
	#      /|\      /|\ \ 
	#     / | \    / | \ \
	#    -2 1  6  7 18 3  4
	#      / \           /| \
	#     9  11         2 1  3
	#       /  \        |
	#      17   12      20
	#                   |
	#                  -6 
	#    -----------------------
	#    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 (4)
	tree.root.child[1].child[3].addChild(2)
	tree.root.child[1].child[3].addChild(1)
	tree.root.child[1].child[3].addChild(3)
	#  Add child node [20] in node (2)
	tree.root.child[1].child[3].child[0].addChild(20)
	#  Add child node [-6] in node (20)
	tree.root.child[1].child[3].child[0].child[0].addChild(-6)
	#  Get tree height
	height = tree.findHeight(tree.root)
	#  Display the calculated height
	print(" Height : ", height, end = "")

if __name__ == "__main__": main()

input

 Height :  6
#  Ruby program for
#  Find height of 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

	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

	#  Returns a maximum value of two numbers
	def max(a, b) 
		if (a > b) 
			return a
		else
 
			return b
		end

	end

	def findHeight(node) 
		if (node == nil) 
			return 0
		end

		i = 0
		height = 0
		#  iterating the child of given node
		while (i < node.child.length) 
			#  Recursively visit child node
			height = self.max(self.findHeight(node.child[i]), height)
			i += 1
		end

		#  return new height
		return height + 1
	end

end

def main() 
	tree = NAryTree.new()
	#           10
	#          /   \
	#         /     \
	#        /       \   
	#       8         5
	#      /|\      /|\ \ 
	#     / | \    / | \ \
	#    -2 1  6  7 18 3  4
	#      / \           /| \
	#     9  11         2 1  3
	#       /  \        |
	#      17   12      20
	#                   |
	#                  -6 
	#    -----------------------
	#    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 (4)
	tree.root.child[1].child[3].addChild(2)
	tree.root.child[1].child[3].addChild(1)
	tree.root.child[1].child[3].addChild(3)
	#  Add child node [20] in node (2)
	tree.root.child[1].child[3].child[0].addChild(20)
	#  Add child node [-6] in node (20)
	tree.root.child[1].child[3].child[0].child[0].addChild(-6)
	#  Get tree height
	height = tree.findHeight(tree.root)
	#  Display the calculated height
	print(" Height : ", height)
end

main()

input

 Height : 6
import scala.collection.mutable._;
// Scala program for
// Find height of 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);
	}
	// Returns a maximum value of two numbers
	def max(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	def findHeight(node: TreeNode): Int = {
		if (node == null)
		{
			return 0;
		}
		var i: Int = 0;
		var height: Int = 0;
		// iterating the child of given node
		while (i < node.child.size)
		{
			// Recursively visit child node
			height = max(findHeight(node.child(i)), height);
			i += 1;
		}
		// return new height
		return height + 1;
	}
}
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      20
		                   |
		                  -6 
		    -----------------------
		    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 (4)
		tree.root.child(1).child(3).addChild(2);
		tree.root.child(1).child(3).addChild(1);
		tree.root.child(1).child(3).addChild(3);
		// Add child node [20] in node (2)
		tree.root.child(1).child(3).child(0).addChild(20);
		// Add child node [-6] in node (20)
		tree.root.child(1).child(3).child(0).child(0).addChild(-6);
		// Get tree height
		var height: Int = tree.findHeight(tree.root);
		// Display the calculated height
		print(" Height : " + height);
	}
}

input

 Height : 6
import Foundation;
// Swift 4 program for
// Find height of n-ary tree
class TreeNode
{
	var key: Int;
	var child: [TreeNode?] ;
	init(_ key: Int)
	{
		self.key = key;
		self.child = [TreeNode]();
	}
	func addChild(_ key: Int)
	{
		let t: TreeNode = TreeNode(key);
		self.child.append(t);
	}
}
class NAryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Returns a maximum value of two numbers
	func max(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	func findHeight(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		var i = 0;
		var height = 0;
		// iterating the child of given node
		while (i < node!.child.count)
		{
			// Recursively visit child node
			height = self.max(self.findHeight(node!.child[i]), height);
			i += 1;
		}
		// return new height
		return height + 1;
	}
}
func main()
{
	let tree = NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	                   |
	                  -6 
	    -----------------------
	    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 (4)
	tree.root!.child[1]!.child[3]!.addChild(2);
	tree.root!.child[1]!.child[3]!.addChild(1);
	tree.root!.child[1]!.child[3]!.addChild(3);
	// Add child node [20] in node (2)
	tree.root!.child[1]!.child[3]!.child[0]!.addChild(20);
	// Add child node [-6] in node (20)
	tree.root!.child[1]!.child[3]!.child[0]!.child[0]!.addChild(-6);
	// Get tree height
	let height = tree.findHeight(tree.root);
	// Display the calculated height
	print(" Height : ", height, terminator: "");
}
main();

input

 Height :  6
// Kotlin program for
// Find height of n-ary tree
class TreeNode
{
	var key: Int;
	var child: MutableList<TreeNode> ;
	constructor(key: Int)
	{
		this.key = key;
		this.child = mutableListOf<TreeNode>();
	}
	fun addChild(key: Int): Unit
	{
		val t: TreeNode = TreeNode(key);
		this.child.add(t);
	}
}
class NAryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Returns a maximum value of two numbers
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	fun findHeight(node: TreeNode ? ): Int
	{
		if (node == null)
		{
			return 0;
		}
		var i: Int = 0;
		var height: Int = 0;
		// iterating the child of given node
		while (i < node.child.size)
		{
			// Recursively visit child node
			height = this.max(this.findHeight(node.child[i]), height);
			i += 1;
		}
		// return new height
		return height + 1;
	}
}
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      20
	                   |
	                  -6 
	    -----------------------
	    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 (4)
	tree.root!!.child[1].child[3].addChild(2);
	tree.root!!.child[1].child[3].addChild(1);
	tree.root!!.child[1].child[3].addChild(3);
	// Add child node [20] in node (2)
	tree.root!!.child[1].child[3].child[0].addChild(20);
	// Add child node [-6] in node (20)
	tree.root!!.child[1].child[3].child[0].child[0].addChild(-6);
	// Get tree height
	var height: Int = tree.findHeight(tree.root);
	// Display the calculated height
	print(" Height : " + height);
}

input

 Height : 6

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.

Last updated on by Kalkicode




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