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