Largest element in an N-ary Tree

Last Updated : 21 Oct, 2024

Given an n-ary tree containing positive node values, the task is to find the node with the largest value in the given n-ary tree.
Note: An n-ary tree is a tree where each node can have zero or more children nodes. Unlike a binary tree, which has at most two children per node (left and right), the n-ary tree allows for multiple branches or children for each node.

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 idea is to traverse the given n-ary tree recursively 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++ Code to find the largest node value in 
// the given N-ary tree using recursion
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    vector<Node*> children;

    Node(int val) {
        data = val;
    }
};

// Recursive function to find the node 
// with the largest value
int findLargestNode(Node* root) {
    
    // Check if the tree is empty
    if (!root) return INT_MIN; 

    // Initialize with root node's value
    int maxVal = root->data;  

    // Recur for all children and
    // find the maximum value
    for (auto child : root->children) {
        maxVal = max(maxVal, findLargestNode(child));
    }

    return maxVal;
}

int main() {
    
    // Representation of given N-ary tree
    //         11
    //       /  |  \
    //     21   29  90
    //    /    /  \   \
    //   18   10  12  77
    Node* root = new Node(11);
    root->children.push_back(new Node(21));
    root->children.push_back(new Node(29));
    root->children.push_back(new Node(90));
    root->children[0]->children.push_back(new Node(18));
    root->children[1]->children.push_back(new Node(10));
    root->children[1]->children.push_back(new Node(12));
    root->children[2]->children.push_back(new Node(77));

    cout << findLargestNode(root) << endl;

    return 0;
}

Java

// Java code to find the largest node value 
// in the given N-ary tree using recursion
import java.util.*;

class Node {
    int data;
    List<Node> children;

    Node(int val) {
        data = val;
        children = new ArrayList<>();
    }
}

// Recursive function to find the node 
// with the largest value
public class GfG {

    public static int findLargestNode(Node root) {
        
        // Check if the tree is empty
        if (root == null) return Integer.MIN_VALUE; 
        
        // Initialize with root node's value
        int maxVal = root.data;  

        // Recur for all children and
        // find the maximum value
        for (Node child : root.children) {
            maxVal = Math.max(maxVal, findLargestNode(child));
        }

        return maxVal;
    }

    public static void main(String[] args) {
        
        // Representation of given N-ary tree
        //         11
        //       /  |  \
        //     21   29  90
        //    /    /  \   \
        //   18   10  12  77
        Node root = new Node(11);
        root.children.add(new Node(21));
        root.children.add(new Node(29));
        root.children.add(new Node(90));
        root.children.get(0).children.add(new Node(18));
        root.children.get(1).children.add(new Node(10));
        root.children.get(1).children.add(new Node(12));
        root.children.get(2).children.add(new Node(77));

        System.out.println(findLargestNode(root));
    }
}

Python

# Python code to find the largest node value 
# in the given N-ary tree using recursion
class Node:
    def __init__(self, val):
        self.data = val
        self.children = []

# Recursive function to find the node 
# with the largest value
def find_largest_node(root):
    
    # Check if the tree is empty
    if root is None:
        return float('-inf')
    
    # Initialize with root node's value
    max_val = root.data  
    
    # Recur for all children and
    # find the maximum value
    for child in root.children:
        max_val = max(max_val, find_largest_node(child))

    return max_val

if __name__ == "__main__":
  
  # Representation of given N-ary tree
  #         11
  #       /  |  \
  #     21   29  90
  #    /    /  \   \
  #   18   10  12  77
  root = Node(11)
  root.children.append(Node(21))
  root.children.append(Node(29))
  root.children.append(Node(90))
  root.children[0].children.append(Node(18))
  root.children[1].children.append(Node(10))
  root.children[1].children.append(Node(12))
  root.children[2].children.append(Node(77))

  print(find_largest_node(root))

// C# code to find the largest node value 
// in the given N-ary tree using recursion
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public List<Node> children;

    public Node(int val) {
        data = val;
        children = new List<Node>();
    }
}

// Recursive function to find the node 
// with the largest value
class GfG {
    public static int FindLargestNode(Node root) {
      
        // Check if the tree is empty
        if (root == null) return int.MinValue; 

        // Initialize with root node's value
        int maxVal = root.data;  

        // Recur for all children and
        // find the maximum value
        foreach (Node child in root.children) {
            maxVal = Math.Max(maxVal,
                            FindLargestNode(child));
        }

        return maxVal;
    }

    public static void Main(string[] args) {
      
        // Representation of given N-ary tree
        //         11
        //       /  |  \
        //     21   29  90
        //    /    /  \   \
        //   18   10  12  77
        Node root = new Node(11);
        root.children.Add(new Node(21));
        root.children.Add(new Node(29));
        root.children.Add(new Node(90));
        root.children[0].children.Add(new Node(18));
        root.children[1].children.Add(new Node(10));
        root.children[1].children.Add(new Node(12));
        root.children[2].children.Add(new Node(77));

        Console.WriteLine(FindLargestNode(root));
    }
}

JavaScript

// JavaScript code to find the largest node value 
// in the given N-ary tree using recursion
class Node {
    constructor(val) {
        this.data = val;
        this.children = [];
    }
}

// Recursive function to find the node 
// with the largest value
function findLargestNode(root) {
    // Check if the tree is empty
    if (root === null) return Number.MIN_SAFE_INTEGER;

    // Initialize with root node's value
    let maxVal = root.data;  

    // Recur for all children and
    // find the maximum value
    for (let child of root.children) {
        maxVal = Math.max(maxVal, findLargestNode(child));
    }

    return maxVal;
}

// Representation of given N-ary tree
//         11
//       /  |  \
//     21   29  90
//    /    /  \   \
//   18   10  12  77
const root = new Node(11);
root.children.push(new Node(21));
root.children.push(new Node(29));
root.children.push(new Node(90));
root.children[0].children.push(new Node(18));
root.children[1].children.push(new Node(10));
root.children[1].children.push(new Node(12));
root.children[2].children.push(new Node(77));

console.log(findLargestNode(root));

Output

Time Complexity: O(n), where n is the number of nodes in the N-ary tree, as each node is visited once.
Auxiliary Space : O(h), where h is the height of the tree.

Second Largest element in n-ary tree

lakshita

Improve

Article Tags :

Practice Tags :

Largest element in an N-ary Tree

Similar Reads

N-ary Tree Traversals

Easy problems on n-ary Tree

Thank You!

What kind of Experience do you want to share?