Binary Search Heap Construction

[kaushik_acharya]

http://poj.org/problem?id=1785

I tried the recursive solution but got stack overflow for last two test case(http://www.informatik.uni-ulm.de/acm/Locals/2004/) (where input size is around 50,000)
My method is as suggested here: http://www.stanford.edu/class/cs97si/assn3.html
i.e. Find the root, divide-and-conquer

Code: Select all

class Node
{
   string label;
   int priority;
   Node* left;
   Node* right;
}

class Treap
{
   std::vector<Node*> vecNode_;
   Node* root_;
}

Node* Treap::construct_treap_recursive(unsigned int beginIndex, unsigned int endIndex)
{
    // create sub-tree of nodes [beginIndex,endIndex) //endIndex excluded
 	// root of the subtree is the node which has highest priority
 	if (endIndex - beginIndex == 1)
	{
          return vecNode_[beginIndex];
      }

        // get the max priority index in the range [beginIndex,endIndex)
        Node* curRoot = vecNode_[maxPriorityIndex];

        if (maxPriorityIndex > beginIndex)
	{
		Node* leftSubtreeRoot = construct_treap_recursive(beginIndex,maxPriorityIndex,str);
		curRoot->setLeft(leftSubtreeRoot);
         }
	
        if (maxPriorityIndex < (endIndex-1))
	{
		Node* rightSubtreeRoot = construct_treap_recursive(maxPriorityIndex+1,endIndex,str);
		curRoot->setRight(rightSubtreeRoot);
        }
       
        return curRoot;
}

//The call:
root_ = construct_treap_recursive(0,vecNode_.size());

Though I haven't written here, but the output string also gets formed during the treap construction.

My question:
a) Recursion is bound to hit stack overflow given the size of data. Am i right?
b) I am not able to figure out how to change this to iterative one. Can anyone give me a hint.
c) Though the treap can be constructed using this: http://en.wikipedia.org/wiki/Cartesian_ ... nstruction
But i wanted to figure out how to do using the method i was trying.