CareerCup

Something like the following:

public Node makeBST(Node head) {
		
		if (head == null) { return null; }

		Node mid = findCenter(head);
		mid.previous.next = null;
		
		mid.previous = makeBST(head);
		mid.next = makeBST(mid.next);
		
		return mid;
	}

	public Node findCenter(Node head) {
	
		//implement
	}

Client will use the BST to represent a set. This probably means that the tree should be more or less ballanced in order to guarantee O(log N) for hasKey() operation. Hence, a root of the tree sould be center of the linked list.
(i) Find the center
(ii) Recursivelly convert lef and right half of the list

public Node dll2bst(Node parent) {
     // Base case
     if (parent == null)            return null;
     Node mid = findMid(parent);
     Node headL = parent;
     Node headR = mid.next;
     mid.prev.next = null;      // break the dll
     // Recursion
     parent.prev = dll2bst(headL);
     parent.next = dll2bst(headR);
     return mid;
}

public Node findMid(Node head) {
     Node aux = head.next;
     while (aux != null && aux.next != null) {
           head = head.next;
           aux   = aux.next.next;
     }
      return head;
}

I guess parent.prev and parent.next should be changed to mid.prev and mid.next in recursion code. Am I right?

The above code doesn't work in Java.

This solution is very similar to the ones already posted, but no one has given a working findMid function (as far as I believe).

n is the length of the list. I use it to calculate how far I should iterate until I reach the mid.

Node *getMid(Node *first, int n) {
	Node *p = first;
	int m = (n-1)/2;
	int i;
	for (i = 0; i < m; ++i) {
		p = p->next;
	}
	return p;
}

Node *makeBST(Node *head, int n) {
	if ((n == 0) || !head) return 0;

	Node *mid = getMid(head, n);
	mid->next = makeBST(mid->next, n - (n-1)/2 - 1);
	mid->prev = makeBST(head, (n-1)/2);
	return mid;
}

Node *findMidDLL(Node *node, int goLeft)
{

    Node *p2; // advance 2 nodes
    Node *p1; // advance 1 node
    p1 = p2 = node;
    int count = 0;
    while (p2 != NULL)
    {
        if (goLeft)
           p2 = p2->left;
        else
           p2 = p2->right;

        count++;

        if (count % 2 == 0)
        {
            if (goLeft)
              p1 = p1->left;
            else
              p1 = p1->right;
        }
    }
    return p1;
}

Node *convertDLLtoBST(Node *node)
{
    if (node == NULL)
        return node;

    Node *prev = node->left;
    Node *next = node->right;
    if (prev)
        prev->right = NULL;
    if (next)
        next->left = NULL;
    Node *leftMidNode = findMidDLL(prev, 1);
    Node *rightMideNode = findMidDLL(next, 0);
    node->left = leftMidNode;
    node->right = rightMideNode;
    printf("on %d left is ", node->data);
    if (leftMidNode)
        printf("%d, right is ", leftMidNode->data);
    else
        printf(" NULL, right is ");

    if (rightMideNode)
        printf("%d\r\n", rightMideNode->data);
    else
        printf(" NULL\r\n");

    convertDLLtoBST(leftMidNode);
    convertDLLtoBST(rightMideNode);
    return node;
}

its a badly written code in terms of what should be static and what should be not. But it works. The basic idea is to take the node in center and make it root and then recursively apply that to the left and right subtree. The LevelOrderTraversal function is just to make sure that my solution worked.

import java.util.*;
public class Convert {

    
    public static void main(String [] args){
//        char [] arr={'g','e','b'};
//        int [] count= {1,2,1};
//        StringBuffer br= new StringBuffer();
//        MakeWords(arr,count,2,br);
        
        int [] arr={12,34,45,56,78,80,84,89,90,92,94};
        nlist head= new nlist();
        head =head.CreateNewList(arr);
        head.ConvertTree();
        nlist root=head.rootNode;
        DoLevelOrderTraversal(root);
    }
    
    public static void DoLevelOrderTraversal(nlist root){
        nlist Dummy= new nlist();
        Queue<nlist> qu= new LinkedList<>();
        if(root==null) return;
        qu.offer(root);
        qu.offer(Dummy);
        while(!qu.isEmpty()){
            nlist out=qu.poll();
            if(out==Dummy){System.out.println();if (!qu.isEmpty()) qu.offer(Dummy);}
            else{
                System.out.print(out.val + " ");
                if (out.prev!=null) {qu.offer(out.prev);}
                if(out.next!=null){qu.offer(out.next);}
                }
            }
        
        
    }
}

class nlist{
    public nlist next;
    public nlist prev;
    public int val;
    public nlist rootNode;
    
    public void ConvertTree(){
        nlist head=this;
        ConvertTreeRec(head,FindSize(head),null,true);
     
    }
    
    
    public  nlist CreateNewList(int [] arr){
        nlist prev=null;
        nlist curr=null;
        nlist FirstOne=null;
        for (int i=0;i<arr.length;i++){
            curr=new nlist();
            curr.val=arr[i];
            if(prev!=null) {prev.next=curr; curr.prev=prev;}
            else { FirstOne=curr;}
            prev=curr;
            curr=null;
        }
        return FirstOne;
    }
    
    public void ConvertTreeRec(nlist Start,int len,nlist parent,boolean isLeft){
        
        nlist toReturn=null;
        if (len<1) return ;
        if (Start==null) return ;
        if (len==1) {
            if(isLeft && parent!=null){
              parent.prev=Start;
              
            }
            else if(parent!=null){
                parent.next=Start;
            }
            if (parent==null){ rootNode=Start;}
            Start.next=null;
            Start.prev=null;
            //return toReturn;
        }
        else{
            int halfLen=len/2;
            int temp=0;
            nlist TempNode=Start;
            while(temp!=halfLen){ temp++; TempNode=TempNode.next;}
            
            if (parent!=null)
              {
                if (!isLeft) {
                    parent.next=TempNode;
                }
                else {parent.prev=TempNode;}
              }
            else {rootNode=TempNode;}
            
            nlist RightNode=TempNode.next;
            TempNode.next=null;
            TempNode.prev=null;
            
            ConvertTreeRec(Start,temp,TempNode,true);
            ConvertTreeRec(RightNode,(len-temp-1),TempNode,false);
        }
        
        
        
    }
    
    public int FindSize(nlist head){
        if (head==null) return  0;
        int size=1;
        nlist temp=head;
        while(temp.next!=null){
            temp=temp.next;
            size++;
        }
        return size;
    }

public class LLToTree{

public static void main(String args[]){
DLL ll = new DLL();
ll.add(new Node(18));
ll.add(new Node(15));
ll.add(new Node(14));
ll.add(new Node(12));
ll.add(new Node(9));
ll.add(new Node(8));
ll.add(new Node(4));
ll.add(new Node(2));
//System.out.println(ll.getEnd().getVal());
ll.traverseTree(ll.change(ll.getRoot().getNext(),ll.getEnd()));

}
}


class DLL{
Node root = new Node(-1);
Node end;
public void setRoot(Node root){
this.root.setNext(root);
}

public Node getRoot(){
return root;
}
public void setEnd(Node n){
this.end = n;
}

public Node getEnd(){
return end;
}
public void add(Node n){
if(getRoot().getNext()== null){
setRoot(n);
setEnd(n);
}else{
n.setNext(getRoot().getNext());
getRoot().getNext().setPrev(n);
n.setPrev(getRoot());
getRoot().setNext(n);

}
}

public void traverse(){
Node temp = root.getNext();
while(temp!=null){
System.out.println(temp.getVal());
temp = temp.getNext();
}
}

public Node change(Node start,Node end){
System.out.println("start is "+start.getVal()+" and end is "+end.getVal());
if(start == end)
return start;
if(start.getNext() ==end){
end.setNext(null);
start.setNext(null);
start.setPrev(null);
return end;
}

if(end.getVal()< start.getVal())
return null;
Node s,d;
s = d = start;
while(d.getNext()!=null){

s = s.getNext();
if(d.getNext().getNext() != null)
d = d.getNext().getNext();
else
d = d.getNext();


}

s.getPrev().setNext(null);
s.getNext().setPrev(null);
//if((start != s.getPrev())
s.setPrev(change(start,s.getPrev()));
//if(change(s.getNext() != end))
s.setNext(change(s.getNext(),end));

return s;
}

public void traverseTree(Node root){
System.out.println(root.getVal());
if(root.getPrev()!=null){
System.out.println("left is "+root.getPrev().getVal());

}else{
System.out.println("left is null");
}
if(root.getNext()!=null){
System.out.println("right is "+root.getNext().getVal());

}else{
System.out.println("right is null");
}
if(root.getPrev()!=null)
traverseTree(root.getPrev());
if(root.getNext()!=null)
traverseTree(root.getNext());

}
}

class Node{
int val;
Node prev,next;
public Node(int val){
this.val = val;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(){
return next;
}
public void setPrev(Node prev){
this.prev = prev;
}
public Node getPrev(){
return prev;
}

public int getVal(){
return val;
}

}

Did any one think about building the tree from bottom.
For example, if I have a list:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Start from the bottom, we set 1 to be a leaf, and 2 be its parent, and the next element to be its brother, we got

tree:
  2
1  3

then we proceed to find the parent of 2, which is the next element of 3.

Tree:
     4
  2
1   3

its easy to recursively fill up the right subtree.

tree:
    4
  2  6
1 3 5 7

I believe this method could save some time finding the mid, how every I do not know how to re balance it if the left sub three could not be filled up
i.e in the example above, if we only have 1 - 10, how can I insert the remaining of the elements to the three above?

DLLnode DLLToBT(DLLnode head) {

		if (head.prev == null && head.next == null)
			return head;

		DLLnode root = findMiddle(head);
		DLLnode headL = head;
		DLLnode headR = root.next;
		root.prev.next = null;
		headR.prev = null;
		root.prev = DLLToBT(headL);
		root.next = DLLToBT(headR);

		return root;
	}

	

	private DLLnode findMiddle(DLLnode head) {
		DLLnode ptrSlow = head;
		DLLnode ptrFast = head;
		while (ptrFast != null && ptrFast.next != null) {
			ptrSlow = ptrSlow.next;
			ptrFast = ptrFast.next.next;
		}
		return ptrSlow;
	}

public Node makeBST(Node head) {

if (head==NULL) return NULL;

Node mid = findMid(head);

//break obsolete connection with overflow proof
if (mid.prev != NULL) mid.prev.next=NULL;
if (mid.next != NULL) mid.next.prev=NULL;

//implicit base case: when mid and head are the same single node, no more recursion is needed
if (mid != head)
{
mid.prev = makeBST(head); // DLinked list's "prev" is re-used as if "left child" in BST - concept conversion
mid.next = makeBST(mid.next);
}

return mid;

}

Node findMid(Node head) {

//... find the middle node in a DLinked List - implementation place holder
}

Algo: implementation in C++, correct error of the previous submission

concept: re-use prev/next concept in DLL as left/right concept in BST

Find the middle node of the DLL (abnormal handling: the middle node is empty, return NULL)
Break the obsolete link of the middle point's neighbourin nodes

If the left sub-DLL is not empty, convert it to BST and return its root to add new connection
If the right sub-DLL is not empty, convert it to BST and return its root to add new connection

return the middle node

run-time complexity: O(n), memory: O(1)

Node* convertDLL2BST(Node* head) {
if (head==NULL) return NULL;

Node* middle = findMid(head);

if (middle->prev!=NULL)
{
middle->prev->next=NULL; //reset obsolete connection during conversion
middle->prev=convertDLL2BST(head); //set the middle node's left child
}
if (middle->next!=NULL)
{
middle->next->prev=NULL; //reset obsolete connection during conversion
middle->next=convertDLL2BST(middle->next); //set the middle node's right child
}
return middle;
}

Node* findMid(Node* head) {
//...find the middle node in a DLL list - implementation placeholder
}