CareerCup

sort the list will make it a BST.

Sort the doubly link list... u will get BST...

You mean when you have a list like 1<->2<->3<->4
you can also consider it as a BST, where the root is one and each node only has a right child?

nope.. i mean, when you have list of 1,2,3,4,5,6,7,8,9
your root wil be at middle element. which is 5 now, left side again make it half n make it left child of 5 . same with right side. select middle element n make it right child of 5. every time you are making it half.

but first elements in the list need to be sorted

What does it mean to turn DL List into a BST in place? What is the data structure to be used? That will make a difference in what you can/cannot do! Should I asssume that each element has 5 pointers (next, previous, parent, left, right) or should I reuse next as right, previous as left with no parent?

In any case, sorting first and then somehow asembling the tree would work. You can use merge sort to sort the list--O(n log n) time. Sorted list is a BST, though a linear one. The above mentioned trick with finding the middle for each half and creating the tree this way would also work.

A possibly simpler solution is to build the tree one node at a time.

Start with empty tree. Grab the first element from the DL list, that's your root.

At each step, you'll have a root of the tree you're building, and the remaining DL list. Remove the first element from the (partial) list, insert it (recursively) in the tree. Repeat until no elements left in the DL list. Running time should be O(n*h) where h is the tree height (log n if random or RB tree).

Example: 7,6,8,4,2,9,5

Considering BST, the left child tree items should be less than the root, and the root should be larger than the right child tree items.

Sounds like a partition operation in quick sort.

1. 7,6,8,4,2,9,5 Choose 7 as root ,and as pivot
2. 6,4,2,5,7,8,9 Then 6,4,2,5 are the left child, and 8,9 are the right child.
3. 6,4,2,5 Choose 6 as root, and as pivot
4. 4,2,5,6 Then 6 is the root and 4,2,5 are the left, no right child
5. 4,2,5 Choose 4 as the root, and as pivot
6. 2,4,5 Then 4 is root, 2's left and 5's right child.
7. 8,9 Choose 8 as the root, and as pivot
8. 8,9 Then 8 is the root and 9's the right child.

Now, we got a BST tree. In fact, it is a quick sort, O(n*lgn).

cur_tree=null
cur_node=list
next_node=list->next
while(next_node)
{
cur_node->previous-=null
cur_node->next=null
insert_tree(root,cur_node)
cur_node=nextnode
next_node=nextnode->next
}

struct node
{
    int v;
    node *prev, *next;
};

node *DdlToBst(node*head)
{
    node *root = null;
    node *cur = head;
    while (cur)
    {
      node *next = cur->next;
      
      if (!root) { root = cur; }
      else { insert(root, cur); }
      cur->prev = cur->next = null;
      
      cur = next;
    }
    return root;
}

void insert(node *root, node *p)
{
    if (p->v < root->v)
    {
        if (!root->prev) { root->prev = p; }
        else { insert(root->prev, p); }
    }
    else
    {
        if(!root->next) { root->next = p; }
        else { insert(root->next, p); }
    }
}

Take the pointer to the start of the DL. Treat the "prev" pointer of the DL node as the "left" (less than) pointer of a BT node and treat the existing "next" pointer of the DL node as the "right (greater than) pointer of thr BT node.

If you want an optimal BT, throw the DL through quicksort (can be done in place with a DL) then use the center as the root. Recursively grab the centers of the left and right sub lists as the roots of the left and right nodes.

If you want a quick BT, and the DL is unsorted, use the first element as the root, then throw each subsequent element in with the basic BT algorithm.

I phrased my first paragraph poorly. I should have said:

Redefine the existing fields of the DL node structure. Treat the "prev" pointer of a DL node as the "left" (less than) pointer of a BT node and treat the "next" pointer of the DL node as the "right (greater than) pointer of a BT node.

use top down recursion.......................