Kth largest element in an N-array Tree

0 0 7 minutes read

Given an N-array Tree consisting of N nodes and an integer K, the task is to find the K^th 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 K^th 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 K^th 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>

Output:

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 zambiatek!