Link copied to clipboard. Share away!

Dismiss

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.

- 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**

×