Kth largest element in an N-array Tree
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 Tree class Node { public : int data; vector<Node*> childs; }; // Stores the minimum element // in the recursive call int largestELe = INT_MIN; // Function to find the largest // element under the range of key void 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 Tree void 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 node Node* newNode( int data) { Node* temp = new Node(); temp->data = data; // Return the created node return temp; } // Driver Code int 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 approach import 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 approach import sys # Structure of N-array Tree class 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 call largestELe = - sys.maxsize # Function to find the largest # element under the range of key def 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 Tree def 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 = 3 KthLargestElement(root, K) # This code is contributed by rameshtravel07. |
C#
// C# program for the above approach using 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> |
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.
Contact Us