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
- Create a class
TreeNode
to represent nodes in the N-ary tree. Include a value and a vector of children. - 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. - 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.
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