you do the same using bottom up approach...complexity would O(n)
On 26 Feb 2012 03:54, "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.
>
--
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.
