Country: United States

Comment hidden because of low score. Click to expand.
6
of 6 vote

Something like the following:

``````public Node makeBST(Node head) {

if (head == null) { return null; }

mid.previous.next = null;

mid.next = makeBST(mid.next);

return mid;
}

//implement
}``````

Comment hidden because of low score. Click to expand.
0

Exactly! Haha, almost the same code. Thought, findMid was kind of tricky to oprimize.

Comment hidden because of low score. Click to expand.
0

whats the effect of making mid.previous.next null?

Comment hidden because of low score. Click to expand.
0

Head will never be null and will generate StackOverflow

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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;

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

Comment hidden because of low score. Click to expand.
0

@autoboli, how did you optimize find minimum? You still have to traverse the list to find it. The whole algorithm would be much more efficient if we build an array first and build a tree from it.

Comment hidden because of low score. Click to expand.
1
of 3 vote

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);
mid.prev.next = null;      // break the dll
// Recursion
return mid;
}

while (aux != null && aux.next != null) {
aux   = aux.next.next;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

great work solution. Only 1 minor bug break the dll need to break on both side of mid

``````mid.prev.next = null;      // break the dll
mid.next.prev = null;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

The above code doesn't work in Java.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

mid->next = makeBST(mid->next, n - (n-1)/2 - 1);
return mid;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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};
DoLevelOrderTraversal(root);
}

public static void DoLevelOrderTraversal(nlist root){
nlist Dummy= new nlist();
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(){

}

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

}

int size=1;
while(temp.next!=null){
temp=temp.next;
size++;
}
return size;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LLToTree{

public static void main(String args[]){
DLL ll = new DLL();
//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;
}
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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

Yes, this is the method i think interviewer is expecting, especially with constraint that you shouldn't be creating the extra Node inside your function.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````DLLnode DLLToBT(DLLnode head) {

root.prev.next = null;

return root;
}

while (ptrFast != null && ptrFast.next != null) {
ptrSlow = ptrSlow.next;
ptrFast = ptrFast.next.next;
}
return ptrSlow;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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
{
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;

}

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

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

//...find the middle node in a DLL list - implementation placeholder
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.