Largest element in an N-ary Tree

Largest element in an N-ary Tree

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++

#include <bits/stdc++.h> using namespace std;    struct Node {     int key;     vector<Node*> child; };    Node* maximum = NULL;    Node* newNode(int key) {     Node* temp = new Node;     temp->key = key;             return temp; }    void findlargest(Node* root) {          if (root == NULL)         return;                  if ((maximum) == NULL)         maximum = root;                  else if (root->key > (maximum)->key) {         maximum = root;     }                  for (int i = 0;          i < root->child.size(); i++) {         findlargest(root->child[i]);     } }    int main() {          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);             cout << maximum->key;        return 0; }

Output:

90

Time Complexity: O(N)
Auxiliary Space: O(1)

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets