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.
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.
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
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)
If you have any feedback about this
article and want to improve this, please write to email@example.com