• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

K’th Largest Element in BST when modification to BST is not allowed

March 19, 2015 by Dhaval Dave

Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

      [20]
      /       
    [8]  [22] 
    /  \
  [5]  [10]
       /  \
     [9]  [12]

For example, in the following BST, if
if k = 3, then output should be 12
if k = 5, then output should be 9.

Method 1)  Brute Force in O(n)

In order of BST gives 5,8,9,10,12,20,22
and print member A[n-k+1] will be out put.

Now Lets discuss tricky way :

As we know that larger elements are in Right Side of a node and smaller in left side for BST.
Can we use this trick ???

Think for above example , R=no if Recursion,
r = 1 we traverse 22 and found that its largest
r = 2 we traverse 20, which is second largest.
r=3 and we went to 12 via 8-10-12 ( first traverse right path always)
so 3rd largest is 12.

So with Post Order Traversal We can find Kth largest in O(k + h) time

So Method 2 ) Post Order Traversal 

Algo . C=Count of node visited, K= Kth number

Function KthLargest(Node *root, int k, int &c)

  1. If root=null or c>= k
    return.
  2. KthLargest ( root->right ,  k, c)
  3. c++
  4. if ( c == k) cout << root -> n;
  5. KthLargest ( root->left ,  k, c)

For queries, suggestion and more questions / solutions please write us at admin@gohired.in

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Binary Search Tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Search element in a matrix with all rows and columns in sorted order

Find the element that appears once others appears thrice

Maximum size of square sub matrix with all 1’s in a binary matrix

Find Percentage of Words matching in Two Strings

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Flipkart SDET Interview Experience

Find min element in Sorted Rotated Array (Without Duplicates)

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

SAP Off Campus Hiring_ March 2015 Computer Skills

Difference between a LinkedList and a Binary Search Tree BST

Amazon Interview On-Campus For Internship – 1

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Count number of ways to reach a given score in a game

Reliance Jio Software Developer Interview Experience

The greedy coins game Dynamic Programming

Calculate price of parking from parking start end time prices

Trapping Rain Water

Regular Expression Matching

Given a float number convert it into the string WITHOUT using any inbuilt Function

Apriori algorithm C Code Data Mining

BlueStone E-commerce Interview Experience

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Introduction To Number Theory ( Part 1 )

Python Array String

Best Java Book | Top Java Programming Book for Beginners

SAP Hiring Off-Campus General Aptitude

Find if a binary tree is height balanced ?

Handle duplicates in Binary Search Tree

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Copyright © 2025 · Genesis Framework · WordPress · Log in