Find Kth Element In Ascending Order And Delete It, Perform Q-Queries

You are given N numbers and Q queries. There is only one query type, you have to print the Kth number when all the remaining numbers are arranged in ascending order. You have to remove that number from the list after a query.

Prerequisite

Balanced BST

Solution

Basic Idea is in-order traversal of BST gives us sorted array.

So we will traverse Balanced BST in in-order fashion and print the number and mark as deleted(put 0 at that place) after printing.



Now we just need to traverse the tree in in-order traversal based on Kth number and how many elements current node contains in left and right subtree.

what all information is required to store in BST Node.

* value : actual element value
* left_nodes : number of nodes in left
* right_nodes : number of nodes in right



for more clarification, See the code.
If anything is not clear in post, you can ask [me]



Problem Link





Ramesh Chandra