• 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

Leetcode: Merge Intervals

C++ OOPs Part1

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Circular Linked List

Find Pythagorean Triplets in an array in O(N)

Amazon Interview On-Campus For Internship – 1

Closed Parentheses checker

Sort Stack in place

Regular Expression Matching

Subset Sum Problem Dynamic programming

Binary Tree in Java

System Design: Designing a LLD for Hotel Booking

Python Dictionaries

Get Minimum element in O(1) from input numbers or Stack

Generic Object Oriented Stack with Template

Implement LRU Cache

Given a string, find the first character which is non-repetitive

DFS (Depth First Search)

Singly linked list

Maximum occurred Smallest integer in n ranges

Printing Longest Common Subsequence

SAP Hiring Off-Campus General Aptitude

Convert number to words java

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

How strtok() Works

Given Set of words or A String find whether chain is possible from these words or not

Find two non repeating elements in an array of repeating elements

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Print vertical sum of all the axis in the given binary tree

C Program for TAIL command of UNIX

Copyright © 2025 · Genesis Framework · WordPress · Log in