Kth Smallest Element in an N-ary Tree
Given an N-array Tree (Generic Tree) and an integer K, the task is to find the Kth smallest element in an N-array Tree.
Examples:
Input: 10
/ / \ \
2 34 56 100
/ \ | / | \
77 88 1 7 8 9
K = 3
Output: 7
Explanation: 7 is the 3rd smallest element in the tree. The first two smallest elements are 1 and 2 respectively.Input: 1
/ \ \
2 3 4
/ \
5 6
K = 4
Output: 4
Approach: The problem can be solved by finding the smallest element in the given range K-times and keep updating the upper end of the range to the smallest element found so far. Follow the steps below to solve the problem:
- Initialize a global variable, say MinimumElement as INT_MAX.
- Declare a function smallestEleUnderRange(root, data) and perform he following operations:
- If root.data is more than data, then update MinimumElement as min of MinimumElement and root.data.
- Iterate over all children of the root. Call recursive function smallestEleUnderRange(child, data).
- Declare a function KthSmallestElement(root, k) to perform the following operations:
- Initialize a variable, say ans as INT_MIN, to store the Kth smallest element.
- Iterate over the range [0, K – 1] using a variable i and perform the following:
- Call smallestEleUnderRange(root, ans) function and then update ans as MinimumElement and then MinimumElement as INT_MAX.
- Finally, print ans as the required answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a node class Node { public : int data; vector<Node*> childs; }; // Global variable set to Maximum int MinimumElement = INT_MAX; // Function that gives the smallest // element under the range of key void smallestEleUnderRange(Node* root, int data) { if (root->data > data) { MinimumElement = min( root->data, MinimumElement); } for (Node* child : root->childs) { smallestEleUnderRange(child, data); } } // Function to find the Kth smallest element int kthSmallestElement(Node* root, int k) { int ans = INT_MIN; for ( int i = 0; i < k; i++) { smallestEleUnderRange(root, ans); ans = MinimumElement; MinimumElement = INT_MAX; } return ans; } // Function to create a new node Node* newNode( int data) { Node* temp = new Node(); temp->data = data; return temp; } // Driver Code int main() { /* Let us create below 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)); cout << kthSmallestElement(root, 3); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Class containing left and // right child of current // node and key value static class Node { public int data; public Vector<Node> childs; public Node( int data) { this .data = data; childs = new Vector<Node>(); } } // Global variable set to Maximum static int MinimumElement = Integer.MAX_VALUE; // Function that gives the smallest // element under the range of key static void smallestEleUnderRange(Node root, int data) { if (root.data > data) { MinimumElement = Math.min(root.data, MinimumElement); } for (Node child : root.childs) { smallestEleUnderRange(child, data); } } // Function to find the Kth smallest element static int kthSmallestElement(Node root, int k) { int ans = Integer.MIN_VALUE; for ( int i = 0 ; i < k; i++) { smallestEleUnderRange(root, ans); ans = MinimumElement; MinimumElement = Integer.MAX_VALUE; } return ans; } // Function to create a new node static Node newNode( int data) { Node temp = new Node(data); return temp; } public static void main(String[] args) { /* Let us create below 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 )); System.out.print(kthSmallestElement(root, 3 )); } } // This code is contributed by mukesh07. |
Python3
# Python3 program for the above approach import sys # Structure of a node class Node: def __init__( self , data): self .data = data self .childs = [] # Global variable set to Maximum MinimumElement = sys.maxsize # Function that gives the smallest # element under the range of key def smallestEleUnderRange(root, data): global MinimumElement if root.data > data: MinimumElement = min (root.data, MinimumElement) for child in range ( len (root.childs)): smallestEleUnderRange(root.childs[child], data) # Function to find the Kth smallest element def kthSmallestElement(root, k): global MinimumElement ans = - sys.maxsize for i in range (k): smallestEleUnderRange(root, ans) ans = MinimumElement MinimumElement = sys.maxsize return ans # Function to create a new node def newNode(data): temp = Node(data) return temp """ Let us create below tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 """ root = newNode( 10 ) (root.childs).append(newNode( 2 )) (root.childs).append(newNode( 34 )) (root.childs).append(newNode( 56 )) (root.childs).append(newNode( 100 )) (root.childs[ 0 ].childs).append(newNode( 77 )) (root.childs[ 0 ].childs).append(newNode( 88 )) (root.childs[ 2 ].childs).append(newNode( 1 )) (root.childs[ 3 ].childs).append(newNode( 7 )) (root.childs[ 3 ].childs).append(newNode( 8 )) (root.childs[ 3 ].childs).append(newNode( 9 )) print (kthSmallestElement(root, 3 )) # This code is contributed by divyesh072019. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Class containing left and // right child of current // node and key value class Node { public int data; public List<Node> childs; public Node( int data) { this .data = data; childs = new List<Node>(); } } // Global variable set to Maximum static int MinimumElement = Int32.MaxValue; // Function that gives the smallest // element under the range of key static void smallestEleUnderRange(Node root, int data) { if (root.data > data) { MinimumElement = Math.Min(root.data, MinimumElement); } foreach (Node child in root.childs) { smallestEleUnderRange(child, data); } } // Function to find the Kth smallest element static int kthSmallestElement(Node root, int k) { int ans = Int32.MinValue; for ( int i = 0; i < k; i++) { smallestEleUnderRange(root, ans); ans = MinimumElement; MinimumElement = Int32.MaxValue; } return ans; } // Function to create a new node static Node newNode( int data) { Node temp = new Node(data); return temp; } static void Main() { /* Let us create below 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)); Console.Write(kthSmallestElement(root, 3)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Structure of a node class Node { constructor(data) { this .childs = []; this .data = data; } } // Global variable set to Maximum let MinimumElement = Number.MAX_VALUE; // Function that gives the smallest // element under the range of key function smallestEleUnderRange(root, data) { if (root.data > data) { MinimumElement = Math.min(root.data, MinimumElement); } for (let child = 0; child < (root.childs).length; child++) { smallestEleUnderRange(root.childs[child], data); } } // Function to find the Kth smallest element function kthSmallestElement(root, k) { let ans = Number.MIN_VALUE; for (let i = 0; i < k; i++) { smallestEleUnderRange(root, ans); ans = MinimumElement; MinimumElement = Number.MAX_VALUE; } return ans; } // Function to create a new node function newNode(data) { let temp = new Node(data); return temp; } /* Let us create below 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)); document.write(kthSmallestElement(root, 3)); // This code is contributed by rameshtravel07. </script> |
7
Time Complexity: O(N * K) where N is the number of nodes in the given tree.
Auxiliary Space: O(1), but the recursion stack uses a maximum of O(N) space.
Contact Us