CareerCup

Pseudo-code

public Node construct(int preorder[]) {
    return construct(preorder, 0, -INF, INF);
}
private <Node, int> construct(int preorder[], int i, int min, int max) {
    if (i >= preorder.length) {
        return <null, i>;
    }
    if (!(preorder[i] <= max && preorder[i] > min)) {
        return <null, i>;
    }
    Node node = new Node(preorder[i++]);
    <node.left, i> = construct(preorder, i, min, node.data);
    <node.right, i> = construct(preorder, i, node.data, max);
    return <node, i>;
}

geeksforgeeks.org/archives/25268

int index = 0;

public Node createBSTPreOrder(int[] a) {
	return build(a, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private Node build(int[] a, int min, int max) {
	Node n = null;
	if (index < a.length && a[index] > min && a[index] < max) {
		n = new Node(a[index++]);
		n.left = build(a, min, n.data);
		n.right = build(a, n.data, max);
	}
	return n;
}

is parent pointer allowed in the bst structure??
if so, its quite simple O(n).

if not then do a modified binary search on the array and get the elements
on the right and left of root, similarly proceed with left and right subtree.

comlexity= logn +2log(n/2)+4log(n/4).... = O(n). (its same as for build heap).

Put the element in to a stack s. O(n).

Pop every element from the stack and put it in either left or right node. you need to keep track of the root node, currentLeftNode and currentRightNode. O(n) time. This is same technique used by compiler to evaluate any expression where roots are operator.

I am assuming the pre order list contains operands and operators otherwise its not possible to build a unique BST.
This can be done in O(n) time by using stacks.

Algorithm:
Read input preorder expression from the end i.e right to left
Run the below loop for the length of the elements in the pre order expression
If the element is an operand push it to stack.
If the element is an operator pop an element from stack. Set it as the left child. Pop another element from stack.Set it as the right child.
Push the operator(containing the left and right childs) to the stack.
Return the last element as the root of the build BST.

Using stack

public Node buildPre(int[] a) {
	Stack<Node> s = new Stack<Node>();
	root = new Node(a[0]);
	s.push(root);
	
	for (int i = 1; i < a.length; i++) {
		Node n = null;
		while(!s.empty() && a[i] > s.peek().data)
			n = s.pop();
		
		if (n == null) {
			s.peek().left = new Node(a[i]);
			s.push(s.peek().left);
		}
		else {
			n.right = new Node(a[i]);
			s.push(n.right);
		}
	}
	return root;
}

First element will be the root and there will be decreasing sequence followed by an increasing sequence. Decreasing sequence will be left subtree and increasing sequence will be right subtree.

Tree(pre[],int start,int end)
     {
             node *ptr=(node *)alloc(sizeof(node));

             ptr->data=pre[start];

             for(int i=start+1;i<end;i++)
                   if(pre[i+1]>pre[i])
                         break;

            ptr->left=Tree(pre,start+1,i)
            ptr->right=Tree(pre,i+1,end)

            retrun ptr;
}

Another approach could be to build the root node using the 0th element in the input array.
Then, iterate over the remaining elements in the input array and insert into the BST.
Thus, we get worst case O(n) for the operation