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

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. 
 


 


Reffered: https://www.geeksforgeeks.org

Tree

Related
Construct a Binary Tree from String with bracket representation | Set 2 Construct a Binary Tree from String with bracket representation | Set 2
Minimum time required to color all edges of a Tree Minimum time required to color all edges of a Tree
Test Case Generation | Set 6 (Random Unweighted Binary Tree) Test Case Generation | Set 6 (Random Unweighted Binary Tree)
Queries to find the sum of weights of all nodes with vertical width from given range in a Binary Tree Queries to find the sum of weights of all nodes with vertical width from given range in a Binary Tree
Median of all nodes from a given range in a Binary Search Tree ( BST ) Median of all nodes from a given range in a Binary Search Tree ( BST )

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 10



 

Horje