Amazon Interview Question
Country: India
myNode * DLLtoBST(myNode *head)
{
if(head == NULL)
return head;
// find the mid
myNode* midNode = FindMid(head);
if(midNode == head)
return head;
if(midNode->prev)
midNode->prev->next = NULL;
if(midNode->next)
midNode->next->prev = NULL;
myNode* leftNode = DLLtoBST(head);
myNode* rightNode = DLLtoBST(midNode->next);
midNode->prev = leftNode;
midNode->next = rightNode;
return midNode;
}
The above code only divides the the list into halves.how it construct a tree i don't understand?.
Return middle is used but they are not stored in a variable;
Please correct me if i am wrong.
Hi
Is this problem solved by repeatedly selecting the middle element - like in binary search ? In that case, I feel it might get us a binary tree tat is balanced - Am I right ?
Pls comment on this piece of code. Thank You.
It does a Binary Search going over the input n times for each parent node. Hence n^2.
Btree* ConstructTreeFromDLList(DLList *dll) {
// Can we assume that there is a head and a tail ?
DLLNode *head = dll->head;
DLLNode *tail = dll->tail;
Btree *root = BuildTree(DLList *dll, head, tail);
return root;
}
Btree * BuildTree(DLList *dll, DLLNode * head, DLLNode *tail) {
// Find mid node having two pointers from head and tail.
// Boundary cases - no head ? no tail ? - here
Node *this = head;
Node *that = tail;
int mid = 0;
while(this != that || this->prev != that || that->next != this) { // Until they have not crossed
this=this->next;
that=that->prev;
mid++;
}
printf(“Mid Node Index=%d \n”, mid);
BTree *root = this = that;
root->left = ConstructTreeFromDLList(head, that->prev);
root->right = ConstructTreeFromDLList(this->next, tail);
return root;
}
instead of this and that u could have use a fast and slow runner pair.looks near and simple
1> we can just go on traversing the sorted list and save pointers to nodes in an array.
2> Now, call on dis method for the start and end index of the array:
add_to_tree(int start, int end){
if (start == end)
{
insert_to_tree(array[end]);
return;
}
if (start+1 == end)
{
insert_to_tree(array[end]);
insert_to_tree(array[start]);
return;
}
insert_to_tree(array[(end-start)/2]);
add_to_tree(start,(end-start)/2 - 1);
add_to_tree((end-start)/2 , end);
}
Here is my solution :
1. traverse a link list using fast forward pointer and find the middle of it.
2. Use middle as root node and then start inserting the left link list as left subtrrees by traversing doubly link list to left from middle.
3. Construct right subtree from link list right part
Here is my solution :
1. traverse a link list using fast forward pointer and find the middle of it.
2. Use middle as root node and then start inserting the left link list as left subtrrees by traversing doubly link list to left from middle.
3. Construct right subtree from link list right part
Comment from OP:
- y2km11 February 25, 2012NODE* convert( NODE* head ) { if( head->next == NULL ) // handle lists of length 1 return head; if( head->next->next ) // handle lists of length 2 head->next->prev = NULL; return head; NODE* middle = MIDDLENODE(head); NODE* middlenext = middle->next; if( middlenext ) middle->next>prev = NULL; middle->next = NULL; convert( head, middle ); convert( middlenext, LASTNODE(head) ); return middle; }