Given an N-ary tree consisting of N nodes, the task is to find the node having the largest value in the given N-ary Tree.
Examples:
Input:
Output: 90
Explanation: The node with the largest value in the tree is 90.Input:
Output: 95
Explanation: The node with the largest value in the tree is 95.
Approach: The given problem can be solved by traversing the given N-ary tree and keeping track of the maximum value of nodes that occurred. After completing the traversal, print the maximum value obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Structure of a// node of N-ary treestruct Node {Â Â Â Â int key;Â Â Â Â vector<Node*> child;};Â
// Stores the node with largest valueNode* maximum = NULL;Â
// Function to create a new NodeNode* newNode(int key){Â Â Â Â Node* temp = new Node;Â Â Â Â temp->key = key;Â
    // Return the newly created node    return temp;}Â
// Function to find the node with// largest value in N-ary treevoid findlargest(Node* root){    // Base Case    if (root == NULL)        return;Â
    // If maximum is NULL, return    // the value of root node    if ((maximum) == NULL)        maximum = root;Â
    // If value of the root is greater    // than maximum, update the maximum node    else if (root->key > (maximum)->key) {        maximum = root;    }Â
    // Recursively call for all the    // children of the root node    for (int i = 0;         i < root->child.size(); i++) {        findlargest(root->child[i]);    }}Â
// Driver Codeint main(){    // Given N-ary tree    Node* root = newNode(11);    (root->child).push_back(newNode(21));    (root->child).push_back(newNode(29));    (root->child).push_back(newNode(90));    (root->child[0]->child).push_back(newNode(18));    (root->child[1]->child).push_back(newNode(10));    (root->child[1]->child).push_back(newNode(12));    (root->child[2]->child).push_back(newNode(77));Â
    findlargest(root);Â
    // Print the largest value    cout << maximum->key;Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
// Structure of a// node of N-ary treestatic class Node {Â Â Â Â int key;Â Â Â Â Vector<Node> child = new Vector<>();};Â
// Stores the node with largest valuestatic Node maximum = null;Â
// Function to create a new Nodestatic Node newNode(int key){Â Â Â Â Node temp = new Node();Â Â Â Â temp.key = key;Â
    // Return the newly created node    return temp;}Â
// Function to find the node with// largest value in N-ary treestatic void findlargest(Node root){         // Base Case    if (root == null)        return;Â
    // If maximum is null, return    // the value of root node    if ((maximum) == null)        maximum = root;Â
    // If value of the root is greater    // than maximum, update the maximum node    else if (root.key > (maximum).key)     {        maximum = root;    }Â
    // Recursively call for all the    // children of the root node    for(int i = 0;            i < root.child.size(); i++)     {        findlargest(root.child.get(i));    }}Â
// Driver Codepublic static void main(String[] args){         // Given N-ary tree    Node root = newNode(11);    (root.child).add(newNode(21));    (root.child).add(newNode(29));    (root.child).add(newNode(90));    (root.child.get(0).child).add(newNode(18));    (root.child.get(1).child).add(newNode(10));    (root.child.get(1).child).add(newNode(12));    (root.child.get(2).child).add(newNode(77));Â
    findlargest(root);Â
    // Print the largest value    System.out.print(maximum.key);}}Â
// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approachÂ
# Structure of a# node of N-ary treeclass Node:    # Constructor to set the data of    # the newly created tree node    def __init__(self, key):        self.key = key        self.child = []Â
# Stores the node with largest valuemaximum = NoneÂ
# Function to create a new Nodedef newNode(key):Â Â Â Â temp = Node(key)Â
    # Return the newly created node    return tempÂ
# Function to find the node with# largest value in N-ary treedef findlargest(root):    global maximum    # Base Case    if (root == None):        returnÂ
    # If maximum is null, return    # the value of root node    if ((maximum) == None):        maximum = rootÂ
    # If value of the root is greater    # than maximum, update the maximum node    elif (root.key > (maximum).key):        maximum = rootÂ
    # Recursively call for all the    # children of the root node    for i in range(len(root.child)):        findlargest(root.child[i])Â
# Given N-ary treeroot = newNode(11)(root.child).append(newNode(21))(root.child).append(newNode(29))(root.child).append(newNode(90))(root.child[0].child).append(newNode(18))(root.child[1].child).append(newNode(10))(root.child[1].child).append(newNode(12))(root.child[2].child).append(newNode(77))Â
findlargest(root)Â
# Print the largest valueprint(maximum.key)Â
# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;Â
public class GFG{Â
// Structure of a// node of N-ary treeclass Node { Â Â Â Â public int key;Â Â Â Â public List<Node> child = new List<Node>();};Â
// Stores the node with largest valuestatic Node maximum = null;Â
// Function to create a new Nodestatic Node newNode(int key){Â Â Â Â Node temp = new Node();Â Â Â Â temp.key = key;Â
    // Return the newly created node    return temp;}Â
// Function to find the node with// largest value in N-ary treestatic void findlargest(Node root){         // Base Case    if (root == null)        return;Â
    // If maximum is null, return    // the value of root node    if ((maximum) == null)        maximum = root;Â
    // If value of the root is greater    // than maximum, update the maximum node    else if (root.key > (maximum).key)     {        maximum = root;    }Â
    // Recursively call for all the    // children of the root node    for(int i = 0;            i < root.child.Count; i++)     {        findlargest(root.child[i]);    }}Â
// Driver Codepublic static void Main(String[] args){         // Given N-ary tree    Node root = newNode(11);    (root.child).Add(newNode(21));    (root.child).Add(newNode(29));    (root.child).Add(newNode(90));    (root.child[0].child).Add(newNode(18));    (root.child[1].child).Add(newNode(10));    (root.child[1].child).Add(newNode(12));    (root.child[2].child).Add(newNode(77));Â
    findlargest(root);Â
    // Print the largest value    Console.Write(maximum.key);}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>    // Javascript program for the above approach         // Structure of a    // node of N-ary tree    class Node    {        constructor(key) {           this.key = key;           this.child = [];        }    }         // Stores the node with largest value    let maximum = null;Â
    // Function to create a new Node    function newNode(key)    {        let temp = new Node(key);Â
        // Return the newly created node        return temp;    }Â
    // Function to find the node with    // largest value in N-ary tree    function findlargest(root)    {Â
        // Base Case        if (root == null)            return;Â
        // If maximum is null, return        // the value of root node        if ((maximum) == null)            maximum = root;Â
        // If value of the root is greater        // than maximum, update the maximum node        else if (root.key > (maximum).key)        {            maximum = root;        }Â
        // Recursively call for all the        // children of the root node        for(let i = 0; i < root.child.length; i++)        {            findlargest(root.child[i]);        }    }         // Given N-ary tree    let root = newNode(11);    (root.child).push(newNode(21));    (root.child).push(newNode(29));    (root.child).push(newNode(90));    (root.child[0].child).push(newNode(18));    (root.child[1].child).push(newNode(10));    (root.child[1].child).push(newNode(12));    (root.child[2].child).push(newNode(77));      findlargest(root);      // Print the largest value    document.write(maximum.key);Â
// This code is contributed by surehs07.</script> |
Output:Â
90
Â
Time Complexity: O(N)
Auxiliary Space: O(N) In the worst case, if the tree is a skewed tree, then the space complexity can be O(n) due to function call stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
