CareerCup

This can be solved in O(n) only. The approach am using is, keep a separate stack of node pointers. Push on the 1st node. Keep on traversing the preorder traversal
1. if the value of stack top is more than the current node value, then make the current node left pointer of stack top.
2. if the value of stack top is less that current node value, keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element.
Push the current node on stack in both the cases.

It may seem like an O(n^2) algo, but we are pushing and popping every element on stack only once so this is O(n) time and space.

Please check ideone.com/VohnS for details

ConstructBST(int pre[],int l,int h)
{
	if(l>h) return NULL;
	temp=getNode(pre[l]);
	if(l==h) return temp;
	for(i=l+1;i<=h;i++)
		if(pre[i]>pre[l])
			break;
	temp->left=ConstructBST(pre,l+1,i-1);
	temp->right=ConstructBST(pre,i,h);
	return temp;
}

//l=size of array
node *buildbst(int pre[], int &start,int min,int max)
{
 if( start>l)
    return NULL;
 if(preorder[start]>max && preorder[start]<min)
    return NULL;
 node *root;
 root=malloc(sizeof(node));
 root->data=pre[start++];
 root->left=buildbst(pre,start,min,root->data);
 root->right=buildbst(pre,start,root->data,max);
 return root;
}
please correct me if i am wrong!

Ok here is an O(n) recursive version, which is hopefully correct, unlike my previous attempt.

Tree Create(Stream <T> preOrder) {
    return CreateInternal(preOrder, T.MinValue, T.MaxValue);
}
   
Tree CreateInternal(Stream <T> preOrder, T min, T max) {
   
    if (!preOrder.hasNext()) return null;
    
    T value = preOrder.peek();
     
    if (value < min || value > max) return null;
     
    Tree root = new Tree(preOrder.next());
   
    root->left = CreateInternal(preOrder, min, value);
    root->right = CreateInternal(preOrder, value, max);
    
    return root;
}

Since each failed peek corresponds to a null node in the tree, this is O(n).

public static class TreeNode{
		public int val;
		public TreeNode left,right;
		
		public TreeNode(int val){
			this.val = val;
		}
		
	}
	
	public static TreeNode construct(int[] arr, int low, int high){
		if(low <= high){
			TreeNode n = new TreeNode(arr[low]);
			int i = low+1;
			while(i < arr.length && arr[i] < arr[low])
				i++;
			n.left = construct(arr,low+1, i-1);
			n.right = construct(arr,i, high);
			return n;
		}
		return null;
	}

At first it seemed like a difficult question. But, if we work out, the pre-order traversal of a BST is one of the possible input order for reconstructing a BST.

It seems ordinary question.. i dont know in conform whether i am right.. its just ordinary insertion of node in BST.

public Tree insert(Tree tree,int element)
{
           if(tree==null )
           {
               tree = new Tree();
               tree.element = element;
               tree.left = tree.right = null;
           }
           else if(element < tree.element)
                   tree.left = insert(tree.left, element);
          else if(element > tree.element)
                   tree.right = insert(tree.right,element);

          return tree;
}

// In main function
for(int i = 0;i< preorder.length;i++)
     tree = insert(tree,preorder[i]);

You can only construct BST if in-order and one of pre-order or post-order traversal is given. You can not construct from just pre-order.

Well, it can be created but it well be as good as a linked list. With in order and one other order.
It seems the interviewer wants to know if you know such concepts and if you ask more questions to get clarity.
But that's just my opinion.

Its like a trick question - One just has the preorder traversal, and we need to build a tree!
If you remember, we can build a tree pretty fine with Preorder and Inorder traversal.
See the Preorder traversal as integer data in array.
And Inorder traversal = Sorted Copy of Array above
Viola! :)

#include<stdio.h>
struct node{
       int data;
       struct node* left;
       struct node* right;
       };
       
struct node* consbst(int pre[],int k,int l)
{
    struct node* tmp=(struct node*)malloc(sizeof(struct node));
    if(l==k)
    {
    tmp->data=pre[k];
    tmp->left=NULL;
    tmp->right=NULL;
    return tmp;
    }
    
    int i=k+1;
    
    while(pre[k]>pre[i]&&i<l)
    i++;
    i--;
    tmp->data=pre[k];
    tmp->left=consbst(pre,k+1,i);
    tmp->right=consbst(pre,i+1,l);
    return tmp;
}
void printinorder(struct node* head)
{
   if(head==NULL)
   return;
   printinorder(head->left);
   printf("%d",head->data);
   printinorder(head->right);  
}
int main()
{
 struct node* tree;  
 int pre[]={6,2,1,4,3,5,8,7,9};
 tree=consbst(pre,0,8);
 printinorder(tree); 
 getch();
}

Fix(int ara[], int len) {
    if(!len) return NULL;
    Node * p = NULL;
    for (int i = 0; i < len; i++ ){
        p = Insert(p, ara[i]);
    }
}

Node * Insert(Node *p, int v) {
    if (!p) {
        p = new Node(v);
    }
    if (p->v <= v)
        p->left = Insert(p->left, v);
    else p->right = Insert(p->right, v);
return p;
}

or you can use double pointer to avoid returning the new node address

BST reconstruct(int[] preorder, int s, int e)
{
if(s==e)
return null;
BST root = new BST(preorder[s]);
if(preorder[s]>preorder[s+1])
{
int r = s + 1;
for(; r<e; r++)
{
if(preorder[s]<preorder[r])
break;
}
root.leftchild = reconstruct(preorder, s, r);
root.leftchild = reconstruct(preorder, r, e);
}
else
{
root.rightchild = reconstruct(preorder, s+1, e);
}

return root;
}

for INORDER


#include<stdio.h>
#include<malloc.h>

typedef struct node{
int data;
struct node *l;
struct node *r;
}node;

node *getnode(int d){
node *temp= (node *)malloc(sizeof(node));
temp->data= d;
temp->l= NULL;
temp->r= NULL;
return temp;
}

node *BST(int A[], int min, int max){
int mid= (min+ max)/ 2;
node *temp;

if(max== min)
return getnode(A[min]);
else {
temp= getnode(A[mid]);
if(mid!= min)
temp->l= BST(A, min, mid-1);

temp->r= BST(A, mid+1, max);
return temp;
}
}
void Inorder(node *root){
if(root){
Inorder(root->l);
printf("%d--", root->data);
Inorder(root->r);
}
}

int main(){
int A[12]= {1, 5, 7, 8 ,9 ,12,13, 19, 25, 26, 27, 31};
node *root= BST(A, 0, 11);

Inorder(root);
return 0;
}

We have O(n) solution to construct BST from a sorted array, why all this fuss here i mean stack and all. correct me if i misunderstood the question.

We cannot construct a binary tree just when pre order is given But in case of BST we can. The reason being, if its a BST you can sort the given order which will be equivalent to inorder for that tree. Then we can use both in preorder and inorder traversal lists to built a BST.

Seems like a simple recursive algorithm will do (which when simulated using the stack will be same as the top voted solution, I suppose)

Tree CreateTreefromPreOrder <T> (Stream <T> preOrder) {
   
    Tree root = null;
    
    if (preOrder.hasNext()) {
        root = new Tree(preOrder.next());
    } 
   
    if (preOrder.hasNext()) {
        T child = preOrder.peek();
        if (root->data > child) {
            root->left = CreateTreeFromPreOrder(preOrder);
        }
    }
    root->right = CreateTreeFromPreOrder(preOrder);
    return root;
}

Node* RebuildBST(vector<int> output)
{
	int n=output.size();
	if(n==0)
		return NULL;
	stack<Node*> myStack;
	int i=0;
	Node* root;
	while(i<n)
	{
		int curVal=output[i];
		Node* preNode=NULL,*prePreNode=NULL;
		while(!myStack.empty())
		{
			preNode=myStack.top();
			if(preNode->val>curVal)
				break;
			prePreNode=myStack.top();
			myStack.pop();
		}
		Node* curNode=new Node;
		curNode->val=output[i];
		curNode->L=NULL;
		curNode->R=NULL;
		if(!preNode)
		{
			root=curNode;
		}
		else if(!prePreNode)
		{
			preNode->L=curNode;
		}
		else
		{
			prePreNode->R=curNode;
		}
		myStack.push(curNode);
		i++;
	}
	return root;
}

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

enum TraversalType {
	PREORDER, INORDER, POSTORDER;
}

public class ConstructTreeBack {
	static Node root = new Node();
	static TraversalType traversalType;

	static void formSubTrees(List<Integer> treeList) {
		if (traversalType.equals(TraversalType.PREORDER)) {
			formSubTreesPreOrder(treeList);
		} /*else if (traversalType.equals(TraversalType.INORDER)) {
			formSubTreesInOrder(treeList);
		} else if (traversalType.equals(TraversalType.POSTORDER)) {
			formSubTreesPostOrder(treeList);
		}  */
		
	}
	
	/*static void formSubTreesInOrder(List<Integer> treeList) {
		
	}
	*/
	static void formSubTreesPreOrder(List<Integer> treeList) {
		List<Integer> leftSubTree = new ArrayList<Integer>();
		List<Integer> rightSubTree = new ArrayList<Integer>();
		
		Iterator<Integer> it = treeList.iterator();

		int rootNodeVal = it.next();
		root.setValue(rootNodeVal);
		root.setRoot(true);

		while (it.hasNext()) {
			int nodeVal = it.next();
			if (rootNodeVal > nodeVal) {
				leftSubTree.add(nodeVal);
			} else if (rootNodeVal < nodeVal) {
				rightSubTree.add(nodeVal);
			}
		}
		
		if (leftSubTree.size() <= 3) {
			Node left = formNode(leftSubTree);
			root.setLeftNode(left);
		} else {
			formSubTreesPreOrder(leftSubTree);
		}
		
		if (rightSubTree.size() <= 3) {
			Node right = formNode(rightSubTree);
			root.setLeftNode(right);
		} else {
			formSubTreesPreOrder(rightSubTree);
		}
	}

	static Node formNode(List<Integer> treeList) {
		Node node = new Node();

		if (traversalType.equals(TraversalType.PREORDER)) {
			if (null != treeList.get(0)) {
				node.setValue(treeList.get(0));
			}
			if (null != treeList.get(1)) {
				node.setLeftNode(new Node(treeList.get(1)));
			}
			if (null != treeList.get(2)) {
				node.setRightNode(new Node(treeList.get(2)));
			}
		}
		if (traversalType.equals(TraversalType.INORDER)) {
			if (null != treeList.get(1)) {
				node.setValue(treeList.get(1));
			}
			if (null != treeList.get(0)) {
				node.setLeftNode(new Node(treeList.get(0)));
			}
			if (null != treeList.get(2)) {
				node.setRightNode(new Node(treeList.get(2)));
			}
		}
		if (traversalType.equals(TraversalType.POSTORDER)) {
			if (null != treeList.get(2)) {
				node.setValue(treeList.get(2));
			}
			if (null != treeList.get(0)) {
				node.setLeftNode(new Node(treeList.get(0)));
			}
			if (null != treeList.get(1)) {
				node.setRightNode(new Node(treeList.get(1)));
			}
		}
		return node;
	}

	public static void main(String[] args) {
		Integer treeArrPreOrder[] = { 4, 2, 1, 3, 6, 5, 7 };
		List<Integer> treeList = Arrays.asList(treeArrPreOrder);
		traversalType = TraversalType.PREORDER;
		root.setValue(treeArrPreOrder[0]);
		root.setRoot(true);

		formSubTrees(treeList);
		System.out.println(root);

	}
}

// order is O(n) : T(n) = 2T(n/2) + log(n)
TreeNode* build_bst(vector<int>& a, int lo, int hi)
{
      if (lo > hi) return NULL;
      // do binary search for first true F F F F F T T T T T  
      //  F corresponds to all elements < a[lo]  and T corresponses > a[lo]. and we to find first True 
      int m = find_ele_greater(a, lo+1, hi, a[lo]);
      TreeNode* root = new TreeNode(a[lo]);
      root->left = build_bst(a, lo+1, m-1);
      root->right = build_bst(a, m, hi);
      return root; 
}

Correct me if I'm wrong, but aren't there many different reconstructions? For example if the array is [1, 2, 3, 4, 5], just two possible reconstructions include
{
5
/
4
/
3
/
2
/
1

AND

3
/ \
2 4
/ \
1 5
}

Plus many more?