One way to think about it: Given an input list with n items, consume the first ceiling((n-1)/2)=floor(n/2) items building the left subtree. Then consume the next item to use for the new tree root. Then consume the rest of the elements, which number n - floor(n/2) - 1 to build the right subtree.
If n = 0, you have the base case, which is to return the empty tree. As code: // Convert the sorted list of n elements with head pointer (*head) to a bst and return the root. NODE *sorted_list_to_bst(NODE **head, int n) { if (n == 0) return NULL; NODE *left_subtree = sorted_list_to_bst(head, n / 2); NODE *root = *head; // head is now the root *head = (*head)->next; // consume head NODE *right_subtree = sorted_list_to_bst(head, n - n/2 - 1) root->prev = left_subtree; // using prev/next for left/right child root->next = right_subtree; return root; } NODE *convert(NODE *head) { int n = 0; for (NODE *p = head; p; p = p->next) n++; return sorted_list_to_bst(&head, n); } This turns out to be an O(n) algorithm. On Feb 25, 5:24 pm, Supraja Jayakumar <suprajasank...@gmail.com> wrote: > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.