Find Kth largest number in a given Binary Tree
Given a Binary Tree consisting of N nodes and a positive integer K, the task is to find the Kth largest number in the given tree.
Examples:
Input: K = 3
1
/ \
2 3
/ \ / \
4 5 6 7
Output: 5
Explanation: The third largest element in the given binary tree is 5.Input: K = 1
1
/ \
2 3
Output: 1
Explanation: The first largest element in the given binary tree is 1.
Naive Approach: Flatten the given binary tree and then sort the array. Print the Kth largest number from this sorted array now.
Efficient Approach: The above approach can be made efficient by storing all the elements of the Tree in a priority queue, as the elements are stored based on the priority order, which is ascending by default. Though the complexity will remain the same as the above approach, here we can avoid the additional sorting step.
Just print the Kth largest element in the priority queue.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Struct binary tree node struct Node { int data; Node *left, *right; }; // Function to create a new node of // the tree Node* newNode( int data) { Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // Utility function to find the Kth // largest element in the given tree int findKthLargest(priority_queue< int , vector< int > >& pq, int k) { // Loop until priority queue is not // empty and K greater than 0 while (--k && !pq.empty()) { pq.pop(); } // If PQ is not empty then return // the top element if (!pq.empty()) { return pq.top(); } // Otherwise, return -1 return -1; } // Function to traverse the given // binary tree void traverse( Node* root, priority_queue< int , vector< int > >& pq) { if (!root) { return ; } // Pushing values in binary tree pq.push(root->data); // Left and Right Recursive Call traverse(root->left, pq); traverse(root->right, pq); } // Function to find the Kth largest // element in the given tree void findKthLargestTree(Node* root, int K) { // Stores all elements tree in PQ priority_queue< int , vector< int > > pq; // Function Call traverse(root, pq); // Function Call cout << findKthLargest(pq, K); } // Driver Code int main() { // Given Input Node* root = newNode(1); root->left = newNode(2); root->left->left = newNode(4); root->left->right = newNode(5); root->right = newNode(3); root->right->right = newNode(7); root->right->left = newNode(6); int K = 3; findKthLargestTree(root, K); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Struct binary tree node static class Node { int data; Node left; Node right; } // Function to create new node of the tree static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = null ; temp.right = null ; return temp; } // Stores all elements tree in PQ static Vector<Integer> pq = new Vector<Integer>(); // Utility function to find the Kth // largest element in the given tree static int findKthLargest( int k) { // Loop until priority queue is not // empty and K greater than 0 --k; while (k > 0 && pq.size() > 0 ) { pq.remove( 0 ); --k; } // If PQ is not empty then return // the top element if (pq.size() > 0 ) { return pq.get( 0 ); } // Otherwise, return -1 return - 1 ; } // Function to traverse the given // binary tree static void traverse(Node root) { if (root == null ) { return ; } // Pushing values in binary tree pq.add(root.data); Collections.sort(pq); Collections.reverse(pq); // Left and Right Recursive Call traverse(root.left); traverse(root.right); } // Function to find the Kth largest // element in the given tree static void findKthLargestTree(Node root, int K) { // Function Call traverse(root); // Function Call System.out.print(findKthLargest(K)); } // Driver code public static void main(String[] args) { // Given Input Node root = newNode( 1 ); root.left = newNode( 2 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.right = newNode( 3 ); root.right.right = newNode( 7 ); root.right.left = newNode( 6 ); int K = 3 ; findKthLargestTree(root, K); } } // This code is contributed by divyesh07. |
Python3
# Python3 program for the above approach class Node: # Struct binary tree node def __init__( self , data): self .data = data self .left = None self .right = None # Stores all elements tree in PQ pq = [] # Utility function to find the Kth # largest element in the given tree def findKthLargest(k): # Loop until priority queue is not # empty and K greater than 0 k - = 1 while (k > 0 and len (pq) > 0 ): pq.pop( 0 ) k - = 1 # If PQ is not empty then return # the top element if len (pq) > 0 : return pq[ 0 ] # Otherwise, return -1 return - 1 # Function to traverse the given # binary tree def traverse(root): if (root = = None ): return # Pushing values in binary tree pq.append(root.data) pq.sort() pq.reverse() # Left and Right Recursive Call traverse(root.left) traverse(root.right) # Function to find the Kth largest # element in the given tree def findKthLargestTree(root, K): # Function Call traverse(root); # Function Call print (findKthLargest(K)) # Given Input root = Node( 1 ) root.left = Node( 2 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right = Node( 3 ) root.right.right = Node( 7 ) root.right.left = Node( 6 ) K = 3 findKthLargestTree(root, K) # This code is contributed by mukesh07. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Struct binary tree node class Node { public int data; public Node left, right; }; // Function to create a new node of the tree static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = null ; temp.right = null ; return temp; } // Stores all elements tree in PQ static List< int > pq = new List< int >(); // Utility function to find the Kth // largest element in the given tree static int findKthLargest( int k) { // Loop until priority queue is not // empty and K greater than 0 --k; while (k > 0 && pq.Count > 0) { pq.RemoveAt(0); --k; } // If PQ is not empty then return // the top element if (pq.Count > 0) { return pq[0]; } // Otherwise, return -1 return -1; } // Function to traverse the given // binary tree static void traverse(Node root) { if (root == null ) { return ; } // Pushing values in binary tree pq.Add(root.data); pq.Sort(); pq.Reverse(); // Left and Right Recursive Call traverse(root.left); traverse(root.right); } // Function to find the Kth largest // element in the given tree static void findKthLargestTree(Node root, int K) { // Function Call traverse(root); // Function Call Console.Write(findKthLargest(K)); } static void Main() { // Given Input Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.right = newNode(7); root.right.left = newNode(6); int K = 3; findKthLargestTree(root, K); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Struct binary tree node class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } // Function to create a new node of the tree function newNode(data) { let temp = new Node(data); return temp; } // Stores all elements tree in PQ let pq = []; // Utility function to find the Kth // largest element in the given tree function findKthLargest(k) { // Loop until priority queue is not // empty and K greater than 0 --k; while (k > 0 && pq.length > 0) { pq.shift(); --k; } // If PQ is not empty then return // the top element if (pq.length > 0) { return pq[0]; } // Otherwise, return -1 return -1; } // Function to traverse the given // binary tree function traverse(root) { if (root == null ) { return ; } // Pushing values in binary tree pq.push(root.data); pq.sort( function (a, b){ return a - b}); pq.reverse(); // Left and Right Recursive Call traverse(root.left); traverse(root.right); } // Function to find the Kth largest // element in the given tree function findKthLargestTree(root, K) { // Function Call traverse(root); // Function Call document.write(findKthLargest(K)); } // Given Input let root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.right = newNode(7); root.right.left = newNode(6); let K = 3; findKthLargestTree(root, K); // This code is contributed by decode2207. </script> |
5
Time Complexity: O((N + K)log N)
Auxiliary Space: O(N)