[algogeeks] Constructing Binary Tree from a sorted Doubly Linked List

[Supraja Jayakumar]

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.

Re: [algogeeks] Constructing Binary Tree from a sorted Doubly Linked List

[atul anand]

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.

Re: [algogeeks] Constructing Binary Tree from a sorted Doubly Linked List

[atul anand]

here how you can do it :-
call construct(head,0,n-1); n=length of linked list

node* construct(node *head,int start,int end)
{
int mid;
if(start  end)
   return NULL;

   mid=(start+end)/2;
   node * tleft=construct(dll,start,mid-1);
   head-next=tleft;
   head=head-next;
   head-prev=construct(dll,mid+1,end);

  return head;

}

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