CareerCup

u may also have a parent pointer

smth along these lines should work:

// A[n] - array containing preorder traversal of a BST
root = new node;
t = root, t->parent = 0;
t->val = A[0], split = t;

for(i = 1; i < n; i++) {
    if(A[i] < t->val) {
        add_left_child(t, A[i]);
        split = t;
        t = t->left;
        continue;
    } 
    // if split  == 0 or A[i] < split->val then just add to the right
    // child of the current node 't' otherwise find another 'split'
    if(split != 0 && A[i] > split->val) {
        t = split;
        while(t->parent != 0) {
            if(A[i] < t->parent->val)
                break;
            t = t->parent;
        }
        split = t;
    }
    add_right_child(t, A[i]);
    t = t->right;
}

guys i have a doubt...
in preorder the first node will be the root right ?
so with first node as root we can construct BST considering other nodes in order using normal BST algo right ????

One can start with first element as root and just follow the BST rules(i.e. go to left if element is less than root, go to right otherwise) for rest of the elements.

CN(v)
	sn* n = new sn()
	n->d = v
	n->l = NULL
	n->r = NULL
	
BT(lo, hi)
	if(lo == hi)
		return CN(a[lo])
	v  = a[lo]
	for each lo +1 to hi
		if(a[i] > v)
			break
	n = CN(lo)
	n->l = BT(lo + 1, i-1)
	n->r = BT(i, hi)

But the problem with a pre-order traversal is that you wont get the exact tree because the order isn't stored in pre-order traversal

For example, consider the BST as follows

Root 6
Lchild of 6: 3
Rchild of 6:9
Lchild of 3: 1
Rchild of 3:4
Lchild of 9:7
Rchild of 9:10

Pre-order Traversal: 6,3,1,4,9,7,10

If the tree is modified such that 4 is the Rchild of 1and rchild of 3 is null then we get the same Pre-order traversal. How do you overcome such problems

public Node tree (char [] ary, int begin, int end) {
	
	if (begin > end || begin < 0) return null;
	
	Node n = new Node(ary[begin]);
	
	int halfIndex = getRightIndex (ary, ary[begin], begin + 1, end);
	n.left = tree (begin + 1, halfIndex - 1);
	n.right = tree (halfIndex, end);
	
	return n;
}



public int getRightIndex (char [] ary, char root, int start, int end) {
	
	for (int i = start; i <= end; i++) {
		if (ary[i] > root) {
			return i;
		}
	}
	return -1;
}

If i did not misunderstand this problem,
With only preorder traversal one can not reconstruct tree.
e.g if for two node traversal is 1,2 there are two trees possible
1 root, 2 r. child,
2 root, 1 left child.

We can construct the BST using preorder and without using any extra space.


typedef vector<int> Array;


Tree* ConstructBST(Array preOrder)
{

int i = 0;

Tree* root = new Tree(preOrder[i]);
i++;

Tree* parent = NULL;

int min = INT_MIN;
int max = INT_MAX;

Tree* cur = root

while(i < preOrder.size() && cur)
{
//left branch
if(preOrder[i] > min && preOrder[i] < cur->val)
{
Tree* left= new Tree(preOrder[i]);
i++;

cur->lptr = left;

//set as parent
left->rptr = cur;

//set the max value
max = cur->val;

// set the current
cur = left;
}
//right branch
else if( preOrder[i] > cur->val && preOrder[i] < max)
{
Tree* right= new Tree(preOrder[i]);
i++;

// take the rptr node as there may be a chance that this may be pointing to it's parent
//node
Tree* parent = cur->rptr;

cur->rptr = right;


//set the min value
min = cur->val;


// set the parent node as current node's parent as we have to go back to that parent node
// once done with this node
if(parent)
{
right->rptr = parent;
}

// set the current
cur = right;



}
// move back to parent
else
{
if(cur)
{
//go back to parent node as we had set right node as parent for left branch

Tree* parent = cur->rptr;

cur->rptr = NULL;

cur = parent;

// set the min value
if(cur->lptr)
{
min = cur->lptr->val;
}
else
{
min = INT_MIN;
}

// set the max value
if(cur->rptr)
{
max = cur->rptr->val;
}
else
{
max = INT_MAX;
}

}
}

}


// set the parent nodes to NULL

while(true)
{
Tree* parent = cur->rptr;

if(parent != NULL && parent->lptr == cur)
{
cur->rptr = NULL;
cur = parent;
}
else
{
break;
}

}


return root;

}

<pre lang="" line="1" title="CodeMonkey56755" class="run-this">//Create a BST of n elements
for(int i=0;i<n;i++){
node *node1 = new node;
node1->left=node1->right=NULL;
cin>>node1->data;

if(!root) { root=node1; continue; }
curr=temp=root;


while(curr){
temp=curr;
if(curr->data >= node1->data)
curr=curr->left;
else if(curr->data < node1->data)
curr = curr->right;
}

if(temp->data > node1->data) temp->left=node1; else temp->right=node1;

} </pre><pre title="CodeMonkey56755" input="yes">
</pre>