Find Kth largest number in a given Binary Tree

0 0 6 minutes read

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

Output:

Time Complexity: O((N + K)log N)
Auxiliary Space: O(N)

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!