## Google Interview Question

**Country:**United States

Haha.. my code was almost the same. Great minds think alike !! :) I also did not bother to implement findCenter or check for base cases (null etc)..

Nice answer, I believe the time complexity is O(nlogn) because you have to find the middle node each time; The following algorithm is O(n) and it works,

Call: ConvertToBST( INT_MAX ) and it returns the BST

```
CNode * current = root;
CNode * ConvertToBST( int n )
{
CNode * root_p = NULL;
if ( n )
{
//Build left side tree
CNode * left = ConvertToBST( n/2 );
if ( current )
{
// Root would the current node
root_p = current;
//Assing Left Tree
root_p->m_prev = left;
//Advance Current
current = current->m_next;
//Assign Right Tree
root_p->m_next = ConvertToBST( n/2 );
}
else
{
// If there is not current, Left tree is the answer
root_p = left;
}
}
return root_p;
}
```

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;
}
```

Is it really working solution? let's say list is A<->B<->C. HeadL is always A and HeadR is always B.

I believe your findMin has the logic wrong. You are going all the way to the end instead of stopping at the middle, no?

No.. Its correct because the return pointer is head which is just half way through the list.

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

}

Something like the following:

- Skor January 10, 2015