Given an N-array Tree consisting of N nodes and an integer K, the task is to find the Kth largest element in the given N-ary Tree.
Examples:
Input: K = 3
Output: 77
Explanation:
The 3rd largest element in the given N-array tree is 77.Input: K = 4
Output: 3
Approach: The given problem can be solved by finding the largest element in the given range for K number of times and keep updating the end of the range to the largest element found so far. Follow the steps below to solve the problem:
- Initialize a variable say, largestELE as INT_MIN.
- Define a function, say largestEleUnderRange(root, data), and perform the following steps:
- If the value of the current root is less than the data, then update the value of largestELe as the maximum of largestELe and the current root’s value.
- Iterate over all children of the current root and recursively call for the function largestEleUnderRange(child, data).
- Initialize a variable say, ans as INT_MAX to store the Kth largest element.
- Iterate over the range [0, K – 1] recursively call for the function largestEleUnderRange(root, ans) and update the value of ans as largestELe and largestELe as INT_MIN.
- After completing the above steps, print the value of ans as the resultant Kth maximum value.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of N-array Treeclass Node {public: int data; vector<Node*> childs;};// Stores the minimum element// in the recursive callint largestELe = INT_MIN;// Function to find the largest// element under the range of keyvoid largestEleUnderRange( Node* root, int data){ // If the current root's value // is less than data if (root->data < data) { largestELe = max(root->data, largestELe); } // Iterate over all the childrens for (Node* child : root->childs) { // Update under current range largestEleUnderRange(child, data); }}// Function to find the Kth Largest// element in the given N-ary Treevoid KthLargestElement(Node* root, int K){ // Stores the resultant // Kth maximum element int ans = INT_MAX; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = INT_MIN; } // Print the result cout << ans;}// Function to create a new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; // Return the created node return temp;}// Driver Codeint main(){ /* Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node* root = newNode(10); (root->childs).push_back(newNode(2)); (root->childs).push_back(newNode(34)); (root->childs).push_back(newNode(56)); (root->childs).push_back(newNode(100)); (root->childs[0]->childs).push_back(newNode(77)); (root->childs[0]->childs).push_back(newNode(88)); (root->childs[2]->childs).push_back(newNode(1)); (root->childs[3]->childs).push_back(newNode(7)); (root->childs[3]->childs).push_back(newNode(8)); (root->childs[3]->childs).push_back(newNode(9)); int K = 3; KthLargestElement(root, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Structure of N-array Tree static class Node { public int data; public Vector<Node> childs = new Vector<Node>(); } // Function to create a new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; return temp; } // Stores the minimum element // in the recursive call static int largestELe = Integer.MIN_VALUE; // Function to find the largest // element under the range of key static void largestEleUnderRange(Node root, int data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.max(root.data, largestELe); } // Iterate over all the childrens for (int child = 0; child < root.childs.size(); child++) { // Update under current range largestEleUnderRange(root.childs.get(child), data); } } // Function to find the Kth Largest // element in the given N-ary Tree static void KthLargestElement(Node root, int K) { // Stores the resultant // Kth maximum element int ans = Integer.MAX_VALUE; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Integer.MIN_VALUE; } // Print the result System.out.print(ans); } public static void main(String[] args) { /* Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node root = newNode(10); (root.childs).add(newNode(2)); (root.childs).add(newNode(34)); (root.childs).add(newNode(56)); (root.childs).add(newNode(100)); (root.childs.get(0).childs).add(newNode(77)); (root.childs.get(0).childs).add(newNode(88)); (root.childs.get(2).childs).add(newNode(1)); (root.childs.get(3).childs).add(newNode(7)); (root.childs.get(3).childs).add(newNode(8)); (root.childs.get(3).childs).add(newNode(9)); int K = 3; KthLargestElement(root, K); }}// This code is contributed by suresh07. |
Python3
# Python3 program for the above approachimport sys# Structure of N-array Treeclass Node: # Constructor to set the data of # the newly created tree node def __init__(self, data): self.data = data self.childs = [] # Stores the minimum element# in the recursive calllargestELe = -sys.maxsize# Function to find the largest# element under the range of keydef largestEleUnderRange(root, data): global largestELe # If the current root's value # is less than data if (root.data < data) : largestELe = max(root.data, largestELe) # Iterate over all the childrens for child in range(len(root.childs)): # Update under current range largestEleUnderRange(root.childs[child], data)# Function to find the Kth Largest# element in the given N-ary Treedef KthLargestElement(root, K): global largestELe # Stores the resultant # Kth maximum element ans = sys.maxsize # Iterate over the range [0, K] for i in range(K): # Recursively call for # finding the maximum element # from the given range largestEleUnderRange(root, ans) # Update the value of # ans and largestEle ans = largestELe largestELe = -sys.maxsize # Print the result print(ans)""" Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9"""root = Node(10)(root.childs).append(Node(2));(root.childs).append(Node(34));(root.childs).append(Node(56));(root.childs).append(Node(100));(root.childs[0].childs).append(Node(77))(root.childs[0].childs).append(Node(88))(root.childs[2].childs).append(Node(1))(root.childs[3].childs).append(Node(7))(root.childs[3].childs).append(Node(8))(root.childs[3].childs).append(Node(9))K = 3KthLargestElement(root, K)# This code is contributed by rameshtravel07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Structure of N-array Tree class Node { public int data; public List<Node> childs = new List<Node>(); }; // Function to create a new node static Node newNode(int data) { Node temp = new Node(); temp.data = data; return temp; } // Stores the minimum element // in the recursive call static int largestELe = Int32.MinValue; // Function to find the largest // element under the range of key static void largestEleUnderRange(Node root, int data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.Max(root.data, largestELe); } // Iterate over all the childrens for (int child = 0; child < root.childs.Count; child++) { // Update under current range largestEleUnderRange(root.childs[child], data); } } // Function to find the Kth Largest // element in the given N-ary Tree static void KthLargestElement(Node root, int K) { // Stores the resultant // Kth maximum element int ans = Int32.MaxValue; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Int32.MinValue; } // Print the result Console.Write(ans); } static void Main() { /* Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node root = newNode(10); (root.childs).Add(newNode(2)); (root.childs).Add(newNode(34)); (root.childs).Add(newNode(56)); (root.childs).Add(newNode(100)); (root.childs[0].childs).Add(newNode(77)); (root.childs[0].childs).Add(newNode(88)); (root.childs[2].childs).Add(newNode(1)); (root.childs[3].childs).Add(newNode(7)); (root.childs[3].childs).Add(newNode(8)); (root.childs[3].childs).Add(newNode(9)); int K = 3; KthLargestElement(root, K); }}// This code is contributed by decode2207. |
Javascript
<script> // JavaScript program for the above approach // Structure of N-array Tree class Node { constructor(data) { this.childs = []; this.data = data; } } // Stores the minimum element // in the recursive call let largestELe = Number.MIN_VALUE; // Function to find the largest // element under the range of key function largestEleUnderRange(root, data) { // If the current root's value // is less than data if (root.data < data) { largestELe = Math.max(root.data, largestELe); } // Iterate over all the childrens for (let child = 0; child < root.childs.length; child++) { // Update under current range largestEleUnderRange(root.childs[child], data); } } // Function to find the Kth Largest // element in the given N-ary Tree function KthLargestElement(root, K) { // Stores the resultant // Kth maximum element let ans = Number.MAX_VALUE; // Iterate over the range [0, K] for (let i = 0; i < K; i++) { // Recursively call for // finding the maximum element // from the given range largestEleUnderRange(root, ans); // Update the value of // ans and largestEle ans = largestELe; largestELe = Number.MIN_VALUE; } // Print the result document.write(ans); } // Function to create a new node function newNode(data) { let temp = new Node(data); // Return the created node return temp; } /* Create below the tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ let root = newNode(10); (root.childs).push(newNode(2)); (root.childs).push(newNode(34)); (root.childs).push(newNode(56)); (root.childs).push(newNode(100)); (root.childs[0].childs).push(newNode(77)); (root.childs[0].childs).push(newNode(88)); (root.childs[2].childs).push(newNode(1)); (root.childs[3].childs).push(newNode(7)); (root.childs[3].childs).push(newNode(8)); (root.childs[3].childs).push(newNode(9)); let K = 3; KthLargestElement(root, K); </script> |
Output:
77
Time Complexity: O(N*K)
Auxiliary Space: O(h) where h is the height of the N-ary tree. This is because the largestELe variable is a global variable and is reused for each recursive call, and the maximum number of function calls on the call stack is equal to the height of the tree.
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!
