Convert linked list into binary search tree?

Question

Given a Circularly doubly linked list... How can i convert it into Binary Search Tree..

The question is found at http://rajeevprasanna.blogspot.com/2011/02/convert-binary-tree-into-doubly-linked.html

I tried to write the code for the same, but it choked!! Please, some suggestions here would be good. Also, how can i find the middle of the linked list.. Please talk in terms of code (C or C++ code) and if possible small example would be good else fine.

Going through the article(URL) that i provided above, BST to Linked List was a good excercise. I tried to follow on the same principal, but my program choked... Please help...

Node ListToTree(Node head)
{
    if(head == NULL)
        return NULL;

    Node hleft = NULL, hright = NULL;

    Node root = head;

    hleft = ListToTree(head->left);
    head->left = NULL;
    root->left = hleft;

    hright = ListToTree(head->right);
    head->right = NULL;
    root->right = hright;

    return root;
}

middle of a "Circularly doubly linked list"? Think about it ... — pmg
– pmg, Commented Mar 30, 2011 at 21:21
Need a reference to the original head and make sure right and left are not equal to it o.O — Joe
– Joe, Commented Mar 30, 2011 at 21:24
Also I am gonna guess by choking you meant that your program crashed with a stack overflow. — Joe
– Joe, Commented Mar 30, 2011 at 21:26
Heh! Do you mean the median? Or do you mean the mean? Or what? I don't mean to be be mean about it. — Pete Wilson
– Pete Wilson, Commented Mar 30, 2011 at 21:26
@pmg - i am trying the same logic, middle of linked list... But could not able to figure out the recursive steps. can you help... — AGeek
– AGeek, Commented Mar 30, 2011 at 21:52

Artem Volkhin · Accepted Answer · 2011-03-31 08:48:47Z

1

class Node {
  Node *prev, *next;
  int value;
}

void listToTree(Node * head) {
    if (head == null)
        return;
    if (head->next == head) {
        head->prev = null;
        head->next = null;
        return head;
    }
    if (head->next->next == head) {
        head->prev = null;
        head->next->next = null;
        head->next->prev = null;
        return head;
    }

    Node *p1 = head, *p2 = head->prev;
    while (p1->value < p2.value)
        p1 = p1->next, p2 = p2->prev;
    Node * root = p1;
    root->prev->next = head;
    root->next->prev = head->prev;
    root->prev = listToTree(head);
    root->next = listToTree(root->next);
    return root;
}

edited Mar 31, 2011 at 8:48

answered Mar 30, 2011 at 21:39

Artem Volkhin

1,3728 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Artem Volkhin Over a year ago

And I assume that list isn't sorted, so every element is inserted to the tree in O(log n) time.

AGeek Over a year ago

List is sorted...... And have to be done, without using extra memmory... Just tweaking with pointers, this is achievable. I am trying to figure it out... read the URL that i posted in the question, and you will get an idea...

Artem Volkhin Over a year ago

I've updated my code, check this. It works again in O(n log n) but without additional memory.

Collectives™ on Stack Overflow

Convert linked list into binary search tree?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related