Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

Re: [algogeeks] Constructing Binary Tree from a sorted Doubly Linked List atul anand Sun Feb 26 00:00:04 2012

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

-- 
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.