Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Program to find the kth maximum element in a binary search tree

Published on 10 Mar 2020

Program to find the kth maximum element in a binary search tree is discussed here. The binary search tree and a positive integer 'k' is given as input and the kth maximum element is produced as output.

kth maximum element in a binary search tree

Algorithm to find the Kth maximum element in a BST


  • Input the binary search tree and the K value from the user.
  • Find the reverse of inorder traversal of the binary search tree.
  • Reverse inorder traversal is done because the traversal all nodes takes place in decreasing order.
  • Keep track of the count of nodes visited while traversing.
  • When the count of the nodes becomes equal to K value, return the node.


Program to find the Kth largest element in a binary search tree is given below.


C
C++

Output
Input - Enter the number of edges : 7 Input the tree : 15 12 l 12 8 l 12 13 r 15 18 r 18 24 r 24 22 l 24 27 r Inorder Tree Traversal : 8 12 13 15 18 22 24 27 Output - K'th largest element is 27 K'th largest element is 24 K'th largest element is 22 K'th largest element is 18 K'th largest element is 15 K'th largest element is 13 K'th largest element is 12


Time complexity: O(n + k)


For traversing n nodes: O(n)

For traversing down to rightmost nodes: O(k)

Overall time complexity: O(n + k)


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in