Hi All
A sorted doubly linked list is given. We are asked to construct a balanced
binary tree.
I have designed an n^2 solution. Kindly comment on it and also suggest
possible improvements and definitely let me know if something is wrong.
Btree* ConstructTreeFromDLList(DLList *dll) {
// Assuming there is a head and 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 using two pointers from head and tail.
// Boundary cases - no head ? no tail ? - handle 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 = BuildTree(head, that->prev);
root->right = BuildTree(this->next, tail);
return root;
}
Thank You
Supraja J
--
U
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
