- n-ary-tree, Recursion, Tree, Tree Traversals, tree-traversal

Largest element in an N-ary Tree

Largest element in an N-ary TreeGiven 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: 90Explanation: The node with the largest value in the tree is 90.Input: Output: 95Explanation: 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 using namespace std;  struct Node {    int key;    vector 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 key;      return 0;}Output:
Time Complexity: O(N)Auxiliary Space: O(1)