# How HEAPULM from spoj can be solved by segment tree.

HEAPULM problem from Spoj can be solved by recursion, by making binary search tree of nodes of sorted priority and then performing an inorder traversal of the BST. But how can it be solved by using segment tree?
This problem is categorized under segment tree in
praveendhinwa’s blog

are you sure that " by making binary search tree of nodes of sorted priority and then performing an inorder traversal of the BST" will work ?

because the value of n here is 50000 which gives TLE as inserting a node may take O(N) (first sample case)!

sorry to keep you waiting!

my approach : first of all i used the fact that inorder traversal leads to a sorted result. so, at first i sort the given nodes in ascending order and then build the tree (which previously takes O(N^2)) in O(N)!

see the node at the root is the node with highest priority(val in my code) and so, i just select the node with highest priority from the sorted list and make it root and since it is a BST so, all the nodes to the left of the curr_index(index of highest priority) belong to the left sub-tree and those which are in the right part belong to the right sub-tree and then recursively build each of the left and right sub-tree.

The segment tree is used to answer the query : what is the position of the node with highest priority in a range(l, r).

hope it helps! if you have any doubts in the code or in understanding approach please comment

1 Like

My approach: I have sorted the array of pairs (containing priority and label) on the basis of increasing priority.
And then tried to make Binary search tree from highest priority pair to lowest priority pair. The inorder traversal of this BST will give the desired answer.

@chan55555

if(p[i].S<p[root->index].S)

here you are comparing with the root but the new root now is t !

1 Like

But, I have already sorted the array of pairs and inserting the nodes with higher priority to the lower priority order. So while inserting a node in BST all other existing nodes will have higher priority than the node being inserted.

sorry mate i didn’t see that. i have updated my answer !

1 Like

Many thanks for pointing that mistake, I was having a hard time debugging my code. But as you have pointed earlier, it’s producing TLE, due to O(N) time complexity of insertion of a node in BST. Now going to read about your approach.