8 of 8
added 13 characters in body

Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the tree when the points are not sorted.

I am thinking of a way to do this, which is as follows:

  1. Construct a BST on the points. Since the points are sorted then it will take O(n) time.

    I followed the approach given in this link for this step.

  2. Check if all the nodes satisfy the min-heap property based on the x-coordinates

This will take O(n) time.

So total time complexity will be O(n)

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates??