Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
in the else after "make A[i] right child of last_top ( last popped element " we should also push it on the stack.
@anonymous - when a[i] == 7, only 6 and 5 will be there in the stack. after the while loop last_top will be 6, so 7 will be inserted as the child of 6.
We really don't need auxiliary stack to construct BST if we have links to parent nodes.
Here is a java implementation without stack:
TreeNode constructBST (List<Integer> preOrderWalk) {
TreeNode root = new TreeNode(preOrderWalk.get(0));
TreeNode n = root;
TreeNode p = null;
for (int i = 1; i < preOrderWalk.size(); i++) {
int key = preOrderWalk.get(i);
if(key < n.key) {
TreeNode left = new TreeNode(key);
left.parent = n;
n.left = left;
p = n;
n = n.left;
}
else {
p = getSuccessor(n);
while(p != null && key > p.key ) {
n = p;
p = getSuccessor(n);
}
TreeNode right = new TreeNode(key);
right.parent = n;
n.right = right;
p = n;
n = n.right;
}
}
return root;
}
struct Node *ConstrucBST(int arr[],int size,int &index,int min,int max)
{
if(index>=size)
return NULL;
struct Node *temp=NULL;
if(arr[index]>min && arr[index]<max)
{
temp=NewNode(arr[index]);
index++;
temp->left=ConstrucBST(arr,size,index,min,temp->data);
temp->right=ConstrucBST(arr,size,index,temp->data,max);
}
return temp;
}
Super logic. This constructs a balanced BST. The algo is that leftmost child is min and rightmost child is max and root always devides it in the midde in balanced BST. So verify if each member of array qualifies for the left pos or right pos accordingly using the min/max range supplied as arguements.
I have tested the code with the given elements. I did not run many tests on it. I believe it will work fine.
The algorithm is similar to the one that checks whether the "given tree is a BST".
Let me know your ideas on this.
#include <iostream>
#include <climits>
using namespace std;
struct node {
int val;
node *left;
node *right;
};
int po[]={9,6,4,3,5,7,8,15,13,14,19}; // pre-order elements
int itr=1;
void buildBST(node *r, int min, int max ) {
if ((po[itr]<r->val) && (po[itr]>min)) {
node *temp=new node;
temp->val=po[itr];
r->left=temp;
itr++;
buildBST(temp,min,r->val);
}
if ((po[itr]>r->val) && (po[itr]<max)) {
node *temp=new node;
temp->val=po[itr];
r->right=temp;
itr++;
buildBST(temp,r->val,max);
}
}
node *build (int l) {
node *root=new node;
root->val=po[0];
buildBST (root, INT_MIN, INT_MAX); // call to build tree
return root;
}
void preordertr(node *r) {
if (r!=NULL) {
cout<<r->val<<endl;
preordertr(r->left);
preordertr(r->right);
}
}
int main() {
int l=sizeof(po)/sizeof(int);
node *root=build(l); // build tree
preordertr(root); // check whether tree is correct
return 0;
}
//input array
int[] arr ;
Stack<Integer> s = new Stack<Integer>();
Node root = new Node(arr[0]);
Node tmp = root;
int index = 1;
while( index < arr.length ){
//left
if(arr[index] < tmp.data){
tmp.left = new Node(arr[index]);
index++;
}else{
if(s.empty() || s.peek() > arr[index] ){//root
tmp.right = new Node(arr[index]);
index++;
}else{
tmp = s.pop();
}
}
}
typedef struct node{
int data;
struct node *left;
struct node *right;
}node;
node *newnode(int x){
node *temp = malloc(sizeof(node));
temp->data = x;
temp->left=temp->right = NULL;
}
node * construst_bst(int arr[],int n){
node *head=NULL,*temp,*new;
if(sizeof(arr)/sizeof(int) != n||n<=0){
printf("Array size and given size of array have mismatch\n");
return(NULL);
}
head = newnode(arr[0]);
temp = head;
if(n==1)
return head;
for(i=1;i<n;i++){
new = newnode(arr[i]);
if(arr[i]<=temp->data){
new->right = temp;
temp->left = new;
temp = new;
}
else{
while(temp){
if(temp->right == NULL){
temp->right = new;
temp = new;
break;
}
else{
if(arr[i]>temp->right->data)
temp = temp->right;
else{
new->right = temp->right;
temp->right = new;
temp = new;
break;
}
}
}
}
}
return(head);
}
BTREE * buildBSTBaseOnPreorder(int a[], int iStart, int iEnd, BTREE *parent)
{
int i=0;
int k=0;
BTREE *p, *q;
if(parent == NULL)
{
p = (BTREE *)malloc(sizeof(BTREE));
p->data = a[iStart];
p->left = NULL;
p->right = NULL;
p->parent = NULL;
}
{
if(parent != NULL)
{
p = (BTREE *)malloc(sizeof(BTREE));
p->data = a[iStart];
p->left = NULL;
p->right = NULL;
p->parent = parent;
if(a[iStart] < parent->data)
{
parent->left = p;
}else
{
parent->right = p;
}
//printf("p->data=%d\n\r", p->data);
}
if(iStart < iEnd)
{
k = a[iStart];
for(i=iStart+1; i<=iEnd; i++)
{
if(k < a[i])
{
break;
}
}
if(iStart+1 == iEnd)
{
buildBSTBaseOnPreorder(a, iEnd, iEnd, p);
}else if(i <= iEnd)
{
buildBSTBaseOnPreorder(a, iStart+1, i-1, p);//build left side
buildBSTBaseOnPreorder(a, i, iEnd, p); //build right side
}
}
}
return p;
}
If the given array is the pre-order of representation of BST, all you need to do is to pass the element of the array into your makeBST function and it will construct the BST.
void *makeBST(struct bst **b, int val, struct bst *p)
{
if(*b==NULL)
{
(*b)=(struct bst*)malloc(sizeof(struct bst));
try
{
if(*b==NULL) throw "Allocation Error";
}catch(const char *s)
{
puts(s);
}
(*b)->data=val;
(*b)->lc=NULL;
(*b)->rc=NULL;
(*b)->parent=p;
}
else
{
struct bst *tmp=(*b);
if((*b)->data>val)
makeBST(&((*b)->lc),val,tmp);
else
makeBST(&((*b)->rc),val,tmp);
}
}
struct node *preorderToBst(int start_index, int min, int max, int &violation_index)
{
if (arr[start_index] < min || arr[start_index] > max) {
violation_index = start_index;
return NULL:
}
else {
struct node *root = make_root(arr[start_index]);
root->left = preorderToBst(start_index+1, min, arr[start_index], violation_index);
start_index = violation_index;
root->right = preorderToBst(start_index, arr[start_index], max, violation_index);
return root;
}
}
public static BinaryTreeNode bstFromPreOrder(int[] inpArray, int start, int end){
if(end < start) return null;
if(end == start) return new BinaryTreeNode(inpArray[start]);
BinaryTreeNode root = new BinaryTreeNode(inpArray[start]);
int leftChild = start+1;
int rightChild = start+1;
while(rightChild <= end && (inpArray[start] > inpArray[rightChild]))
rightChild++;
if(rightChild<=end)
root.right = bstFromPreOrder(inpArray, rightChild, end);
if(rightChild != leftChild)
root.left = bstFromPreOrder(inpArray, leftChild, rightChild-1);
return root;
}
No need to have inorder. You can split at the number which is greater than root to get the right subtree. Ex: 53214768 is preorder,
1. First make root with first element 5 as root.
2. Search for element greater than 5. Thats where your right subtree starts from.
3. 3214 is the left subtree and 768 is right subtree
4. Apply the above recursilvely to left and right subtrees.
To Construct any binary tree we need to know either preorder / postorder along with in order.
In this case preorder is given. Also we know that tree is a BST. So, in order will be the sorted array. So, sort the array. Now you have both in order and pre order. Now it is easy to construct the tree.
node *ins(struct node *p,int num){
if(p==NULL) {
p=(struct node*)malloc(sizeof(struct node));
p->left=p->right=NULL;
p->data=num;
return p;}
else {
if(p->data>num)
p->left=ins(p->left,num);
else
p->right=ins(p->right,num);}
return p; }
as preorder is a travesal od pattern DLR the first number will be the node
Use an auxiliary stack S. Suppose given preorder traversal array is A[ 1..N ]
Push A[1] in S. Make A[1] as root of BST For each A[i] : If A[i] <= S.top(): make A[i] left child of element at the top of stack else while S is not empty and A[i] > S.top: last_top = S.pop() make A[i] right child of last_top ( last popped element ) push A[i] in SAs each array element is pushed and popped once only => O(N)
- Cerberuz November 29, 2012