CareerCup

Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.

Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}
 
BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

copied from leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

// prev = left, next = right

node * doublylinkedlisttobst(node * head)
// head -> prev == NULL
{
node * root = head;
head = head->next;
root->next = NULL;
while( head )
{
node * p = root;
while(1)
{
if( p->val > head->val )
{
if( p->prev) p = p->prev;
else { p->prev = head;break;}
}
else
{ if( p-> next) p = p->next;
else { p->next = head;break;}
}
}
p = head;
head = head->next;
p->prev = p->next = NULL;

}
return root;
}

a linked list is a binary-tree with branch factor equal to 1 for every node, except leaf nodes.

And a binary search tree of n nodes can always transformed to the other one by n rotations.

use a recursive kinda approach...
convert(....)
{
find the middle node of the list...(this is the root of tree)
call convert(..) again for nodes to the left of middle node
call convert(..) again for nodes to the right of middle node
adjust the pointers of the middle node(left and right)
}

<pre lang="java" line="1" title="CodeMonkey2481" class="run-this">//To covert a sorted doubly linked list to binary search tree
//Lots of boiler plate for DLL and BST for the actual code is only 5 lines
class DoubleLinkedListNode{
int item;
DoubleLinkedListNode next;
DoubleLinkedListNode prev;
public DoubleLinkedListNode(int item) {
this.item=item;
next=null;
prev=null;
}
@Override
public String toString(){
StringBuilder sb=new StringBuilder();
if(this.prev==null)
sb.append("X--");
else
sb.append(this.prev.item+"--");
sb.append(this.item);
if(this.next==null)
sb.append("--X");
else
sb.append("--"+this.next.item);
return sb.toString();
}
}
class DoubleLinkedList{
int size;
DoubleLinkedListNode head;
public DoubleLinkedListNode getNode(int num){
if(num<0)
return null;
DoubleLinkedListNode cur=head;
int i=0;
while(cur!=null){
if(i==num)
return cur;
i++;
cur=cur.next;
}
return cur;
}
}
class BinarySearchTreeNode{
int item;
BinarySearchTreeNode leftChild;
BinarySearchTreeNode rightChild;
public BinarySearchTreeNode(int item) {
this.item=item;
leftChild=null;
rightChild=null;
}
public BinarySearchTreeNode(){}
@Override
public String toString(){
StringBuilder sb=new StringBuilder();
if(this.leftChild==null)
sb.append("X--");
else
sb.append(this.leftChild.item+"--");
sb.append(this.item);
if(this.rightChild==null)
sb.append("--X");
else
sb.append("--"+this.rightChild.item);
return sb.toString();
}
}

class DLLtoBST {
public static void main(String args[]){
DoubleLinkedListNode d4=new DoubleLinkedListNode(13);
DoubleLinkedListNode d3=new DoubleLinkedListNode(11);
DoubleLinkedListNode d2=new DoubleLinkedListNode(9);
DoubleLinkedListNode d1=new DoubleLinkedListNode(7);
DoubleLinkedListNode d0=new DoubleLinkedListNode(3);
d0.next=d1;d0.prev=null;
d1.prev=d0;d1.next=d2;
d2.prev=d1;d2.next=d3;
d3.prev=d2;d3.next=d4;
d4.prev=d3;d4.next=null;
DoubleLinkedList dll=new DoubleLinkedList();
dll.head=d0;

DLLtoBST db=new DLLtoBST();

BinarySearchTreeNode root =db.createBST(dll,0,4);
System.out.println(root);
System.out.println(root.leftChild);
System.out.println(root.leftChild.rightChild);
System.out.println(root.rightChild);
System.out.println(root.rightChild.rightChild);
}

private BinarySearchTreeNode createBST(DoubleLinkedList dll, int start, int end) {
BinarySearchTreeNode root= new BinarySearchTreeNode();
if(start<=end){
int mid=(start+end)/2;
DoubleLinkedListNode cur=dll.getNode(mid);
root=new BinarySearchTreeNode(cur.item);
root.leftChild=createBST(dll, start, mid-1);
root.rightChild=createBST(dll,mid+1,end);
}
return root;
}

}
</pre><pre title="CodeMonkey2481" input="yes">
</pre>

@prolific.coder -Thanks a ton for this code.

1) sort doubly linked list - ascending
2) add the middle one as root
3) add left middle one as left child
4) add right middle one as right child

Opposite of this problem: cslibrary [.] stanford [.] edu [/] 109 [/] TreeListRecursion [.] html
The list is circular in this problem. For us it is not.

root pointer points to the root of the tree
Current pointer points to the currently processing node
make the first element as root element
root -> next = root -> prev = NULL
current = root -> next
while ( current ! = NULL)
temp = root
while(temp != null) {
if(current.element < temp. element) // goes in to the left tree
{
if(temp.left == null) {
temp.left = current
break
}
temp = temp.left
}
else if( current.element > temp.element) // right tree
{
if(temp.right == null) {
temp.right = current
break
}
temp = temp.right
}
}

/**
Assumptions made:
1) The Node class used for the BST is the same as that of the doubly linked list
2) The tree generated will be of minimal height
3) There is a method (getSize()).that allows us to get the size of the doubly linked list.

**/
public Node getBST(Node doubleList){
if(doubleList==null||doubleList.getSize()==0)
{
return null;
}
int mid=doubleList.getSize()/2;
int i=0;
Node f=doubleList;
Node s=doubleList;
//For each node from node at index 0 to node at index mid remove all the forward pointers ("next" pointers).
while(i<mid)
{
f=s.next();
s.next()=null;
s=f;
i++;
}

//For each node from index=mid to doubleList.getSize()-1, remove all of the reverse pointers ("prev" pointers).
while(s.next()!=null){
s=s.next();
s.prev()=null;
}
return doubleList;

}

Time complexity: O(n)

Complete running Code in java ::

1. Time Complexity - O(nLogn)
2. Space Complexity - O(1) (Not considering recursion stack in space complexity)

public Node sortedListToBst()
    {
        Node temp=h;
        int n=countNodes();
       
       return formBalancedBST_inPlace_nlogn(temp,n);
//    return formBalancedBST_outPlace_n(temp, n);//formBalancedBST_inPlace_nlogn(temp,n);
    }
   
    
    // In place conversion of DLL to Balanced BST
   // Space Complexity : O(1)  
   // Time complexity: O(n)   
    //In-place conversion of Sorted DLL to Balanced BST
    // The tree must be constructed in-place (No new DoublyLinkedNode should be
    //allocated for tree conversion)
    public Node formBalancedBST_inPlace_nlogn(Node head,int n)
    {
        // Base case
        if(n<=0)
            return null;
        
         else if(n==1)
         {
            head.next = null;
            head.prev = null;
            return head;
         }
        
         int i=1;
        Node current = head;
        
         while(i <= n/2)
         {
            current = current.next;
            i++;
         }
          current.prev= formBalancedBST_inPlace_nlogn(head, i-1);
          current.next = formBalancedBST_inPlace_nlogn(current.next, n-i);
                
          return current;
    }

Is there a particular root we want? Or else, I am not sure why the list is doubly linked...

is the doubly linked list sorted? If so, it is easy to convert to a BST.

I think "in place" here signifies that there is no other data structure used.
next will act as right child
prev will act as left child.

we will traverse the doubly linked list and adjust the next prev accordingly.
Also, We might need to change the pointer as to suffice the properties of BST.

Will look into more.

Please comment.