Skip to main content

Minimum value node having maximum depth in an N-ary Tree

Embark on a journey into the realm of N-ary trees as we unveil the process of identifying the minimum value node located at the maximum depth within these intricate structures. Through a comprehensive breakdown of the problem, an innovative solution strategy, and practical Java code implementation, readers will gain a profound understanding of how to tackle this challenging task.

Problem Statement

Given an N-ary tree, the task is to find the minimum value node that resides at the maximum depth of the tree.

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

The output is:

Minimum node at maximum depth: 12

Solution Strategy

  1. Create a class TreeNode to represent nodes in the N-ary tree. Include a value and a vector of children.
  2. Implement the NAryTree class, responsible for building the N-ary tree, finding the height, locating the minimum node at maximum depth, and displaying the result.
  3. Use a recursive approach to traverse the tree while maintaining track of both depth and minimum value node found at maximum depth.

Code Solution

import java.util.Vector;
import java.util.ArrayList;
// Java program for
// Minimum value node having maximum depth 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 > ();
	}
	public void addChild(int key)
	{
		TreeNode t = new TreeNode(key);
		this.child.add(t);
	}
}
public class NAryTree
{
	public TreeNode root;
	public int result;
	public NAryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	public int findHeight(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		int i = 0;
		int depth = 0;
		// iterating the child of given node
		while (i < node.child.size())
		{
			// Recursively visit child node
			depth = max(findHeight(node.child.get(i)), depth);
			i++;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	public void minNode(TreeNode node, int depth)
	{
		if (depth == 1)
		{
			if (this.result > node.key)
			{
				// Get the value of resultant node
				this.result = node.key;
			}
		}
		else
		{
			int i = 0;
			// iterating the child of given node
			while (i < node.child.size())
			{
				// Recursively visit child node
				minNode(node.child.get(i), depth - 1);
				i++;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	public void minValueMaxDepth()
	{
		if (this.root == null)
		{
			return;
		}
		// Find the height of tree
		int depth = findHeight(this.root);
		if (depth == 1)
		{
			// When single node exists in tree
			this.result = this.root.key;
		}
		else
		{
			this.result = Integer.MAX_VALUE;
			// Find minimum node
			minNode(this.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		System.out.print(" Minimum node at maximum depth : " + this.result);
	}
	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
		    
		    -----------------------
		    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);
		tree.minValueMaxDepth();
	}
}

input

 Minimum node at maximum depth : 12
// Include header file
#include <iostream>
#include <limits.h>
#include <vector>

using namespace std;

// C++ program for
// Minimum value node having maximum depth in an 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;
	int result;
	NAryTree()
	{
		this->root = NULL;
		this->result = 0;
	}
	int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	int findHeight(TreeNode *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		int i = 0;
		int depth = 0;
		// iterating the child of given node
		while (i < node->child.size())
		{
			// Recursively visit child node
			depth = this->max(this->findHeight(node->child.at(i)), depth);
			i++;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	void minNode(TreeNode *node, int depth)
	{
		if (depth == 1)
		{
			if (this->result > node->key)
			{
				// Get the value of resultant node
				this->result = node->key;
			}
		}
		else
		{
			int i = 0;
			// iterating the child of given node
			while (i < node->child.size())
			{
				// Recursively visit child node
				this->minNode(node->child.at(i), depth - 1);
				i++;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	void minValueMaxDepth()
	{
		if (this->root == NULL)
		{
			return;
		}
		// Find the height of tree
		int depth = this->findHeight(this->root);
		if (depth == 1)
		{
			// When single node exists in tree
			this->result = this->root->key;
		}
		else
		{
			this->result = INT_MAX;
			// Find minimum node
			this->minNode(this->root, depth);
		}
		// Display the minimum value in maximum depth nodes
		cout << " Minimum node at maximum depth : " << this->result;
	}
};
int main()
{
	NAryTree *tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	    
	    -----------------------
	    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);
	tree->minValueMaxDepth();
	return 0;
}

input

 Minimum node at maximum depth : 12
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Minimum value node having maximum depth 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 > ();
	}
	public void addChild(int key)
	{
		TreeNode t = new TreeNode(key);
		this.child.Add(t);
	}
}
public class NAryTree
{
	public TreeNode root;
	public int result;
	public NAryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	public int findHeight(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		int i = 0;
		int depth = 0;
		// iterating the child of given node
		while (i < node.child.Count)
		{
			// Recursively visit child node
			depth = this.max(this.findHeight(node.child[i]), depth);
			i++;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	public void minNode(TreeNode node, int depth)
	{
		if (depth == 1)
		{
			if (this.result > node.key)
			{
				// Get the value of resultant node
				this.result = node.key;
			}
		}
		else
		{
			int i = 0;
			// iterating the child of given node
			while (i < node.child.Count)
			{
				// Recursively visit child node
				this.minNode(node.child[i], depth - 1);
				i++;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	public void minValueMaxDepth()
	{
		if (this.root == null)
		{
			return;
		}
		// Find the height of tree
		int depth = this.findHeight(this.root);
		if (depth == 1)
		{
			// When single node exists in tree
			this.result = this.root.key;
		}
		else
		{
			this.result = int.MaxValue;
			// Find minimum node
			this.minNode(this.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		Console.Write(" Minimum node at maximum depth : " + this.result);
	}
	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
		    
		    -----------------------
		    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);
		tree.minValueMaxDepth();
	}
}

input

 Minimum node at maximum depth : 12
<?php
// Php program for
// Minimum value node having maximum depth in an 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 $result;
	public	function __construct()
	{
		$this->root = NULL;
		$this->result = 0;
	}
	public	function max($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Returns the height of n ary tree
	public	function findHeight($node)
	{
		if ($node == NULL)
		{
			return 0;
		}
		$i = 0;
		$depth = 0;
		// iterating the child of given node
		while ($i < count($node->child))
		{
			// Recursively visit child node
			$depth = $this->max($this->findHeight($node->child[$i]), $depth);
			$i++;
		}
		return $depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	public	function minNode($node, $depth)
	{
		if ($depth == 1)
		{
			if ($this->result > $node->key)
			{
				// Get the value of resultant node
				$this->result = $node->key;
			}
		}
		else
		{
			$i = 0;
			// iterating the child of given node
			while ($i < count($node->child))
			{
				// Recursively visit child node
				$this->minNode($node->child[$i], $depth - 1);
				$i++;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	public	function minValueMaxDepth()
	{
		if ($this->root == NULL)
		{
			return;
		}
		// Find the height of tree
		$depth = $this->findHeight($this->root);
		if ($depth == 1)
		{
			// When single node exists in tree
			$this->result = $this->root->key;
		}
		else
		{
			$this->result = PHP_INT_MAX;
			// Find minimum node
			$this->minNode($this->root, $depth);
		}
		// Display the minimum value in maximum depth nodes
		echo(" Minimum node at maximum depth : ".$this->result);
	}
}

function main()
{
	$tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	    
	    -----------------------
	    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);
	$tree->minValueMaxDepth();
}
main();

input

 Minimum node at maximum depth : 12
// Node JS program for
// Minimum value node having maximum depth in an 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;
		this.result = 0;
	}
	max(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	findHeight(node)
	{
		if (node == null)
		{
			return 0;
		}
		var i = 0;
		var depth = 0;
		// iterating the child of given node
		while (i < node.child.length)
		{
			// Recursively visit child node
			depth = this.max(this.findHeight(node.child[i]), depth);
			i++;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	minNode(node, depth)
	{
		if (depth == 1)
		{
			if (this.result > node.key)
			{
				// Get the value of resultant node
				this.result = node.key;
			}
		}
		else
		{
			var i = 0;
			// iterating the child of given node
			while (i < node.child.length)
			{
				// Recursively visit child node
				this.minNode(node.child[i], depth - 1);
				i++;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	minValueMaxDepth()
	{
		if (this.root == null)
		{
			return;
		}
		// Find the height of tree
		var depth = this.findHeight(this.root);
		if (depth == 1)
		{
			// When single node exists in tree
			this.result = this.root.key;
		}
		else
		{
			this.result = Number.MAX_VALUE;
			// Find minimum node
			this.minNode(this.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		process.stdout.write(" Minimum node at maximum depth : " + this.result);
	}
}

function main()
{
	var tree = new NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	    
	    -----------------------
	    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);
	tree.minValueMaxDepth();
}
main();

input

 Minimum node at maximum depth : 12
import sys
#  Python 3 program for
#  Minimum value node having maximum depth in an 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
		self.result = 0
	
	def max(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Returns the height of n ary tree
	def findHeight(self, node) :
		if (node == None) :
			return 0
		
		i = 0
		depth = 0
		#  iterating the child of given node
		while (i < len(node.child)) :
			#  Recursively visit child node
			depth = self.max(self.findHeight(node.child[i]), depth)
			i += 1
		
		return depth + 1
	
	#  Find minimum node in maximum depth using recursion
	def minNode(self, node, depth) :
		if (depth == 1) :
			if (self.result > node.key) :
				#  Get the value of resultant node
				self.result = node.key
			
		else :
			i = 0
			#  iterating the child of given node
			while (i < len(node.child)) :
				#  Recursively visit child node
				self.minNode(node.child[i], depth - 1)
				i += 1
			
		
	
	#  Handles the request to find minimum node in maximum depth
	def minValueMaxDepth(self) :
		if (self.root == None) :
			return
		
		#  Find the height of tree
		depth = self.findHeight(self.root)
		if (depth == 1) :
			#  When single node exists in tree
			self.result = self.root.key
		else :
			self.result = sys.maxsize
			#  Find minimum node
			self.minNode(self.root, depth)
		
		#  Display the minimum value in maximum depth nodes
		print(" Minimum node at maximum depth : ", self.result, end = "")
	

def main() :
	tree = NAryTree()
	#           10
	#          /   \
	#         /     \
	#        /       \   
	#       8         5
	#      /|\      /|\ \ 
	#     / | \    / | \ \
	#    -2 1  6  7 18 3  4
	#      / \           /| \
	#     9  11         2 1  3
	#       /  \        |
	#      17   12      20
	#    -----------------------
	#    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)
	tree.minValueMaxDepth()

if __name__ == "__main__": main()

input

 Minimum node at maximum depth :  12
#  Ruby program for
#  Minimum value node having maximum depth 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

	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, :result
	attr_accessor :root, :result
	def initialize() 
		self.root = nil
		self.result = 0
	end

	def max(a, b) 
		if (a > b) 
			return a
		else
 
			return b
		end

	end

	#  Returns the height of n ary tree
	def findHeight(node) 
		if (node == nil) 
			return 0
		end

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

		return depth + 1
	end

	#  Find minimum node in maximum depth using recursion
	def minNode(node, depth) 
		if (depth == 1) 
			if (self.result > node.key) 
				#  Get the value of resultant node
				self.result = node.key
			end

		else
 
			i = 0
			#  iterating the child of given node
			while (i < node.child.length) 
				#  Recursively visit child node
				self.minNode(node.child[i], depth - 1)
				i += 1
			end

		end

	end

	#  Handles the request to find minimum node in maximum depth
	def minValueMaxDepth() 
		if (self.root == nil) 
			return
		end

		#  Find the height of tree
		depth = self.findHeight(self.root)
		if (depth == 1) 
			#  When single node exists in tree
			self.result = self.root.key
		else
 
			self.result = (2 ** (0. size * 8 - 2))
			#  Find minimum node
			self.minNode(self.root, depth)
		end

		#  Display the minimum value in maximum depth nodes
		print(" Minimum node at maximum depth : ", self.result)
	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
	#    -----------------------
	#    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)
	tree.minValueMaxDepth()
end

main()

input

 Minimum node at maximum depth : 12
import scala.collection.mutable._;
// Scala program for
// Minimum value node having maximum depth in an N-ary Tree
class TreeNode(var key: Int,
	var child: ArrayBuffer[TreeNode])
{
	def this(key: Int)
	{
		this(key, new ArrayBuffer[TreeNode]());
	}
	def addChild(key: Int): Unit = {
		var t: TreeNode = new TreeNode(key);
		this.child += t;
	}
}
class NAryTree(var root: TreeNode, var result: Int)
{
	def this()
	{
		this(null,0);
	}
	def max(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	def findHeight(node: TreeNode): Int = {
		if (node == null)
		{
			return 0;
		}
		var i: Int = 0;
		var depth: Int = 0;
		// iterating the child of given node
		while (i < node.child.size)
		{
			// Recursively visit child node
			depth = max(findHeight(node.child(i)), depth);
			i += 1;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	def minNode(node: TreeNode, depth: Int): Unit = {
		if (depth == 1)
		{
			if (this.result > node.key)
			{
				// Get the value of resultant node
				this.result = node.key;
			}
		}
		else
		{
			var i: Int = 0;
			// iterating the child of given node
			while (i < node.child.size)
			{
				// Recursively visit child node
				minNode(node.child(i), depth - 1);
				i += 1;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	def minValueMaxDepth(): Unit = {
		if (this.root == null)
		{
			return;
		}
		// Find the height of tree
		var depth: Int = findHeight(this.root);
		if (depth == 1)
		{
			// When single node exists in tree
			this.result = this.root.key;
		}
		else
		{
			this.result = Int.MaxValue;
			// Find minimum node
			minNode(this.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		print(" Minimum node at maximum depth : " + this.result);
	}
}
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
		    
		    -----------------------
		    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);
		tree.minValueMaxDepth();
	}
}

input

 Minimum node at maximum depth : 12
import Foundation;
// Swift 4 program for
// Minimum value node having maximum depth in an 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(key);
		self.child.append(t);
	}
}
class NAryTree
{
	var root: TreeNode? ;
	var result: Int;
	init()
	{
		self.root = nil;
		self.result = 0;
	}
	func max(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	func findHeight(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		var i = 0;
		var depth = 0;
		// iterating the child of given node
		while (i < node!.child.count)
		{
			// Recursively visit child node
			depth = self.max(self.findHeight(node!.child[i]), depth);
			i += 1;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	func minNode(_ node: TreeNode? , _ depth : Int)
	{
		if (depth == 1)
		{
			if (self.result > node!.key)
			{
				// Get the value of resultant node
				self.result = node!.key;
			}
		}
		else
		{
			var i = 0;
			// iterating the child of given node
			while (i < node!.child.count)
			{
				// Recursively visit child node
				self.minNode(node!.child[i], depth - 1);
				i += 1;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	func minValueMaxDepth()
	{
		if (self.root == nil)
		{
			return;
		}
		// Find the height of tree
		let depth = self.findHeight(self.root);
		if (depth == 1)
		{
			// When single node exists in tree
			self.result = self.root!.key;
		}
		else
		{
			self.result = Int.max;
			// Find minimum node
			self.minNode(self.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		print(" Minimum node at maximum depth : ", self.result, terminator: "");
	}
}
func main()
{
	let tree = NAryTree();
	/*
	           10
	          /   \
	         /     \
	        /       \   
	       8         5
	      /|\      /|\ \ 
	     / | \    / | \ \
	    -2 1  6  7 18 3  4
	      / \           /| \
	     9  11         2 1  3
	       /  \        |
	      17   12      20
	    
	    -----------------------
	    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);
	tree.minValueMaxDepth();
}
main();

input

 Minimum node at maximum depth :  12
// Kotlin program for
// Minimum value node having maximum depth in an 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 ? ;
	var result: Int;
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the height of n ary tree
	fun findHeight(node: TreeNode ? ): Int
	{
		if (node == null)
		{
			return 0;
		}
		var i: Int = 0;
		var depth: Int = 0;
		// iterating the child of given node
		while (i < node.child.size)
		{
			// Recursively visit child node
			depth = this.max(this.findHeight(node.child[i]), depth);
			i += 1;
		}
		return depth + 1;
	}
	// Find minimum node in maximum depth using recursion
	fun minNode(node: TreeNode ? , depth : Int): Unit
	{
		if (depth == 1)
		{
			if (this.result > node!!.key)
			{
				// Get the value of resultant node
				this.result = node.key;
			}
		}
		else
		{
			var i: Int = 0;
			// iterating the child of given node
			while (i < node!!.child.size)
			{
				// Recursively visit child node
				this.minNode(node.child[i], depth - 1);
				i += 1;
			}
		}
	}
	// Handles the request to find minimum node in maximum depth
	fun minValueMaxDepth(): Unit
	{
		if (this.root == null)
		{
			return;
		}
		// Find the height of tree
		var depth: Int = this.findHeight(this.root);
		if (depth == 1)
		{
			// When single node exists in tree
			this.result = this.root!!.key;
		}
		else
		{
			this.result = Int.MAX_VALUE;
			// Find minimum node
			this.minNode(this.root, depth);
		}
		// Display the minimum value in maximum depth nodes
		print(" Minimum node at maximum depth : " + this.result);
	}
}
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
	    
	    -----------------------
	    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);
	tree.minValueMaxDepth();
}

input

 Minimum node at maximum depth : 12

Time Complexity Analysis

The worst-case time complexity is O(n), where n is the number of nodes in the tree. This is because the code involves traversing all nodes of the tree once to compute the height and then again to find the minimum node at the maximum depth.





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