Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,endPre);
//--> it should be
root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,inPre);
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct nodetype
{
int val;
struct nodetype *l,*r;
};
typedef struct nodetype node_type;
node_type *construct_tree(int *in, int *pre, int s, int e)
{
static int i = 0;
if(s>e) return NULL;
node_type *n = (node_type*) malloc(sizeof(node_type));
n->val = pre[i];
n->l = n->r = NULL;
i++;
if( s == e )
return n;
else
{
int ind = search(in,n->val,s,e);
n->l = construct_tree(in,pre,s,ind-1);
n->r = construct_tree(in,pre,ind+1,e);
}
return n;
}
int search(int *in, int ele, int s, int e)
{
int i;
for(i=s;i<e;i++)
if( ele == in[i] )
return i;
}
void postorder(node_type *root)
{
if(root)
{
postorder(root->l);
postorder(root->r);
printf("%d ",root->val);
}
}
main()
{
int in[] = { 5, 15, 18, 20, 22, 25, 30 }, pre[] = { 20, 15, 5, 18, 25, 22, 30 };
node_type *root;
root = construct_tree(in,pre,0,6);
postorder(root);
printf("\n");
}
C++ version.
#include<vector>
#include<algorigth>
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(){}
TreeNode(int data, TreeNode* left=NULL, TreeNode* right=NULL):
data(data), left(left), right(right) {}
};
typedef std::vector<int> OrderList;
typedef OrderList::iterator OrderIterator;
TreeNode *constructFromInorderPreorder(const OrderList& inorder,
const OrderList& preorder) {
return _constructFromInorderPreorder(inorder.begin(), inorder.end(),
preorder.begin(), preorder.end());
}
TreeNode *_constructFromInorderPreorder(
OrderIterator ibegin, OrderIterator iend,
OrderIterator pbegin, OrderIterator pend) {
if(ibegin == iend){
return NULL;
}
int pivot = *pbegin;
OrderIterator pivotPosInInorder = std::find(ibegin, iend, pivot);
int leftSubTreeSize = pivotPosInInorder - ibegin;
TreeNode root = new TreeNode(pivot);
root->left = _constructFromInorderPreorder(
ibegin, pivotPosInInorder,
pbegin + 1, pbegin + (1 + leftSubTreeSize)
);
root->right = _constructFromInorderPreorder(
pivotPosInInorder + 1, iend,
pbegin + (1 + leftSubTreeSize), pend
);
return root;
}
/*
1. Scan pre-order from left to right and search the encountered node in given in-order array.
2. Store position of element in pos.
3. Construct node having value inorder[pos].
4. Divide inorder in left (start, pos-1) and right (pos+1,end).
*/
private int[] preOrder = {50,30,20,40,35,45,70,60,80};
private int[] inOrder = {20,30,35,40,45,50,60,70,80};
private int prePos = 0;
public int searchInOrder(int s , int e , int n)
{
for(int i =s ; i <= e; i++)
{
if(inOrder[i] == n)
return i;
}
return -1;
}
public BSTNode createTree(int start, int end)
{
if(prePos >= preOrder.length)
return null;
BSTNode newNode = new BSTNode();
newNode.setData(preOrder[prePos++]);
if(start == end)
{
return newNode;
}
int pos = searchInOrder(start,end,newNode.getData());
newNode.setLeftChild(createTree(start, pos-1));
newNode.setRightChild(createTree(pos+1, end));
return newNode;
}
public void buildTree()
{
prePos = 0;
root = createTree(0,preOrder.length-1);
}
BST tree = new BST();
tree.buildTree();
public static Node constructBST(int[] inorder, int[] preorder, int p, int r, int lIdx)
{
if (p > r )
return null;
if (p == r)
return new Node(inorder[p]);
int rootIndx = getIndxInInorderTraversal(preorder, preorder[lIdx]);
Node root = new Node(inorder[rootIndx]);
root.left = constructBST(inorder, preorder, p, rootIndx-1, lIdx+1);
root.right = constructBST(inorder, preorder, rootIndx+1, r, lIdx+1);
return root;
}
public static int getIndxInInorderTraversal(int[] preorder, int key)
{
int indx = 0;
for(int i = 0; i < preorder.length; i++)
{
if (preorder[i] == key)
{
indx = i;
break;
}
}
return indx;
}
T(n) = 2*T(n/2) + O(log(n))
TreeNode* constructBST(int in[], int pre[], int n)
{
if (n==0) return NULL;
TreeNode* root = new TreeNode(pre[0]);
int idx = binary_search(in, 0, pre[0]);
if (idx != -1)
{
root->left = constructBST(in, pre+1, idx);
root->right = constructBST(in+idx+1, pre+1+idx, n-1-idx);
}
return root;
}
node* construct_tree(string inorder, string preorder)
{
if(inorder.length() == 1)
{
return new node(inorder[0]);
}
node* root = new node(preorder[0]);
int i = 0, j = 0;
while(i < preorder.length())
{
if(inorder[j++] != preorder[i++])
{
break;
}
}
node* leftSub = construct_tree(inorder.substr(0, i + 1), preorder.substr(j, i + 1));
root->left = leftSub;
node* rightSub = construct_tree(inorder.substr(i + 2, inorder.length() - i - 1), preorder.substr(j + 1, preorder.length() - j));
root->right = rightSub;
}
Just made use of the basic approach to construction of trees from inorder
and preorder traversals.
- Sibendu Dey July 12, 2013#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; struct node { int data; struct node *left; struct node *right; }; struct node * constructTree(int *preorder,int startPre,int endPre,int *inorder,int startIn,int endIn) { if( startPre>endPre || startIn>endIn) return NULL; int temp=preorder[startPre]; int rootIndex; for(rootIndex=startIn;rootIndex<=endIn;rootIndex++) { if(inorder[rootIndex]==temp) { break; } } struct node *root=(struct node *)malloc(sizeof(struct node)); root->data=inorder[rootIndex]; root->left=constructTree(preorder,startPre+1,startPre+rootIndex-startIn,inorder,startIn,rootIndex-1); root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,endPre); return root; } void displayTree(struct node *root) { if(root==NULL) return; displayTree(root->left); cout<<root->data<<" "; displayTree(root->right); } int main() { int preorder[]={30,13,23,14,25,50,45,40,60}; int inorder[]={13,14,23,25,30,40,45,50,60}; struct node *root=NULL; root=constructTree(preorder,0,8,inorder,0,8); displayTree(root); return 0; }