CareerCup

What does it mean by no extra space? Does it mean that we should not use any extra space for creating the BST nodes, rather the BST nodes are already given the pre-order list, we just have to set the left and right childs properly.

Or is it that except for creating BST nodes we should not use any extra space?

Some thoughts
1. Sort the elements to get the Inorder (Remember that a BST sorted is same as its in order)
2. Use the Inorder and Pre/Post order to make the tree. This is discussed many times.

It Can't be solved with only one order ..
It must given ( Inorder and Pre/Post-order ).

To convert a preorder traversal to BST, following are the conditions:
1.First element will be root.
2.LeftChild=nearest element less than root
3. RightChild=nearest element greater than root

<pre lang="" line="1" title="CodeMonkey30417" class="run-this">TreeNode* ConstructFromPreOrder(int pre[], int i, int j, int size)
{
if(i<=j)
{
TreeNode* root = new TreeNode();
root->data = pre[i];
int k = FindLeftSubtree(pre, i, j, root->data, size);
root->left = ConstructFromPreOrder(pre, i+1, k, size);
root->right = ConstructFromPreOrder(pre, k+1, j, size);
return root;
}
return NULL;
}

int FindLeftSubtree(int pre[], int i, int j, int root, int size)
{
int k = i;
for(; pre[k] <= root && k <size; ++k) ;
return k-1;
}</pre><pre title="CodeMonkey30417" input="yes">
</pre>

Sort the elements to get inorder traversal sequence.
With preorder and inorder, you can construct the BST

/*
Given preorder traversal of a BST. Build the BST.
*/

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct tree{
int val;
struct tree *left;
struct tree *right;
}tree;

tree* insert(tree* root, int val)
{
if(root == NULL)
{
tree* temp = (tree*) malloc(sizeof(tree));
temp->val = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}

tree* node = (tree*) malloc(sizeof(tree));
if(root->val < val)
root->right = insert(root->right, val);
else
root->left = insert(root->left, val);
return root;
}

tree* buildBST(int preOrder[], int length)
{
tree* root;
if(length != 0)
{
root = (tree*) malloc(sizeof(tree));
root->val = preOrder[0];
root->left = NULL;
root->right = NULL;
}
else
return NULL;

for(int i = 1; i < length; i++)
{
root = insert(root, preOrder[i]);
}

return root;
}

void printInOrder(tree* BST)
{
if(BST == NULL) return;
printInOrder(BST->left);
cout << BST->val << " ";
printInOrder(BST->right);
}

void printPreOrder(tree* BST)
{
if(BST == NULL) return;
cout << BST->val << " ";
printPreOrder(BST->left);
printPreOrder(BST->right);
}


int main(void)
{
int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12};
tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int));
printInOrder(BST);
cout << endl;
printPreOrder(BST);
cout << endl;
}