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!
