Adobe Interview Question
Member Technical StaffsCountry: United States
Sorry.. forgot something..
function node findMinAfterPrevious():
minNode = null
reverseTraversal(root, Interger.MAX, minNode)
return minNode
Also an O(n^2) complexity.. but think this is clearer, though.
@game boy...if we reach prev node..wat does this mean?does it mean the current inorder node with which we are going to swap the node returned by the revrse inorder??correct if m getting it wrng
@rahul
Yes, What I have as ReverseOrder is exactly the mirror version of inorder traversal. So the previousNode means:
1. In inorder traversal, every node left to previousNode is sorted! i.e. part of BST
2. In reversed inorder traversal, every node right to previousNode is not sorted so finding the min one actually means the next node to swap.
This is the key part why this would work. Well.. at least I suppose so.
I came up with
Consider a BT as an array and apply selection sort.
I will do inorder traversal and while accessing particular node i will call
Inorder_min fxn..
Inorder_min fxn will search the min value from the tree and i will swap it with current index/node.
Now when we encounter the second node then again same fxn will be called and now it will return the secind minimum value and then i will swap these two value and so on..
0(n^2).
Any thoughts on my approach?And any better sol?
We may need to change every node's data but we can not change the tree's shape, so my idea is:
(1)Inorder traverse the tree and save every node's data and pointers into two arrays. Here we do inorder traverse is because BST's inorder traversal is an sorted sequence.
(2)Sort the data array.
(3)Assign data array's elements to pointer array's data fields.
Time: O(Nlog(N))
Space: O(N)
I have an approach.
Given binary tree with root node *rootBin;
1. Traverse the given binary tree by any traversal methods and push the node value to a linked list. Make sure that the nodes are pushed in sorted manner.
2. Now we have a linked list in sorted order
3. Now write a function binaryToBST which takes actual pointer to root node of binary tree.
Traverse the tree in in order traversal format. similary get the sorted values from list one by one.
binaryToBST(rootNode->left);
rootNode->data = (*head)->value; // value is from linked list
*head = (*head)->next;
binaryToBST(rootNode->right);
I didnt write the entire code. I will update the code once I write and test it.
i) convert Binary tree into array
ii) sort it
iii) using inorder traversal place the numbers it won't change the form of tree
#define MAX 6 //max size of the Binary tree
int compare(const void *a,const void *b){ //for quiksort
return *(int*)a-*(int*)b;
}
struct node{
int x;
node* right;
node* left;
};
/* just creating Binary tree out of an array */
node* convert(int a[],int i){
if(i-1<MAX){
node *root=(node*)malloc(sizeof(node));
if(root==NULL)
return NULL;
root->x=a[i-1];
root->left=convert(a,i*2);
root->right=convert(a,i*2+1);
return root;
}
return NULL;
}
/* through inorder traversal place the sorted form of array */
void inorder(node*root,int a[],int &i){
if(root!=NULL){
inorder(root->left,a,i);
root->x=a[i++];
inorder(root->right,a,i);
}
}
/* using queue to print level by level for finding the difference between binary tree and BST */
void q(node* root){
node* a[MAX+1];
int f=0,r=0;
a[r++]=root;
while(r!=f){
printf("%d ",a[f++]->x);
if(a[f-1]->left)
a[r++]=a[f-1]->left;
if(a[f-1]->right)
a[r++]=a[f-1]->right;
}
}
int main() {
int a[]={5,6,7,2,1,4},i=0;
printf("in BS form:\n");
while(i<MAX)
printf("%d ",a[i++]);
i=0;
node *root=convert(a,1);
qsort(a,MAX,sizeof(a[0]),compare);
inorder(root,a,i);
printf("\nin BST form:\n");
q(root);
return 0;
}
Run quicksort on it, but instead iterating over an array do inorder iteration over the tree (the second pointer should iterate 'inorder backwards').
Complexity:
- selectiong comparison key O(1) - take root for example
- iterate to next\prev - O(1) - assuming nodes have pointer to parent. Otherwise it would not be possible to traverse the tree at all in constant memory
- swap O(1)
So the complexity is the same is for regular qsort - asymptotic O(n log n), pessimistic O(n^2) in const memory (in-place)
1. Make a tree clone of BT in respect to the structure.
2. New tree will store no. of node present in left and right subtree.
3. Now change BT to Double Link List.
4. Sort DLL .
5. construct BST using data of New constructed tree.
space O(n), time O(n)
Didn't quite understand rahul's idea.
Inorder traversal of a BST is in increasing order, so we can do a inorder, while finding the min in reverse order then swap them:
- gameboy1024 December 05, 2013