CareerCup

There are 2 ways:
1) Calculate Mid Point of Linked list for which you would traverse the entire LL and then that Mid point will be Root. Left elements of LL will be left child and Right will be right child.
After that repeat the same cycle for Left LL and same for Right LL. This has more run time since this will have cost of traversing LL and finding Mid elements.

2) In second approach, we are are good with space complexity, then we can just read all elements of LL into an array and then construct the tree. Finding mid element in an array is just O(1) so that will save time. And then we can construct the tree.

Nice approach!

what i undertand by applying binary search here is to make center of list, the root node of every subtree . correct me if i am wrong.

This code truncates the first and the last element of the DLL (I have no idea why). Add a dummy first and last element and then it works fine.

public static final double LOG2= Math.log(2);
    
    public static DoublyLinkedList.Node traverse(DoublyLinkedList.Node node, int offset)
    {
        DoublyLinkedList.Node temp= node;
        if(offset>=0)
            while(offset-->0)
                temp= temp.next;
        else
            while(offset++<0)
                temp=temp.prev;
        return temp;
    }
    
    public static int getRootPos(int size)
    {
        int treeHeight= (int)(Math.ceil(Math.log(size)/LOG2));
        return (int)(Math.pow(2,treeHeight)/2);
    }
    
    public static void buildTree(DoublyLinkedList.Node root, int size,  int leftSize)
    {
            if(size<=1)
            {
                if(root!=null)
                {
                root.next= null;
                root.prev= null;
                }
                return;
            }
             
            int leftLeftSize= getRootPos(leftSize);
            DoublyLinkedList.Node leftSubtreeRoot=null;
            if(leftLeftSize>0)
            {
            leftSubtreeRoot= traverse(root, leftLeftSize-leftSize);
            buildTree(leftSubtreeRoot, leftSize, leftLeftSize);
            }
            
            int rightLeftSize= getRootPos(size-leftSize);
            DoublyLinkedList.Node rightSubtreeRoot= null;
            if(rightLeftSize>0)
            {
            rightSubtreeRoot= traverse(root, rightLeftSize);
            buildTree(rightSubtreeRoot, size-leftSize, rightLeftSize);
            }
            
            root.prev= leftSubtreeRoot;
            root.next= rightSubtreeRoot;        
    }

This problem can be done in an easier way...
First, travel through the list and store the elements in an array, then that array is also sorted in ascending order.
Second, define a function as follows (pseudo-code) :-

form_btree(int *a, int i, int j)
         {
                    if (i==j)
                    tree_insert(a[i]);
                    else
                    {
                                tree_insert(a[(int)(i+j)/2]);
                                if(i==(i+j)/2)
                                form_tree(a,i,j);
                                else
                                {
                                      form_btree(a,i,(i+j)/2-1);
                                      form_btree(a,(i+j)/2+1,j);
                                }
                      }
           }

where tree_insert is name of the function for inserting a value into the binary tree

31 void BST::createBSTfromSortedList(BSTNode *&pRoot, Node *head, int len) {
 32     if(head==0||len<=0) return;
 33
 34     int midNum = (len-1)/2;
 35     int i = 0;
 36     Node *p = head;
 37     while(i<midNum) {
 38         p = p->next;
 39         i++;
 40     }
 41     if(pRoot==0) pRoot = new BSTNode();
 42     pRoot->value = p->value;
 43     createBSTfromSortedList(pRoot->left, head, midNum);
 44     createBSTfromSortedList(pRoot->right, p->next, len-midNum-1);
 45 }

First, traverse this link list and store all the value into an array;
Secondly, build balanced BT in recursion method as below(simple and cool right?):

BTREE * buildBSTBaseSortedArray(int a[], int h, int t)
{
BTREE *middle;

if(h<t)
{
middle = (BTREE *)malloc(sizeof(BTREE));
middle->data = a[(t+h)/2];
middle->parent = NULL;
middle->left = buildBSTBaseSortedArray(a, h, (t+h)/2-1);//left child;
middle->right = buildBSTBaseSortedArray(a, (t+h)/2+1, t);//rihgt child;
return middle;
}else if(h==t)
{
middle = (BTREE *)malloc(sizeof(BTREE));
middle->data = a[h];
middle->parent = NULL;
middle->left = NULL;
middle->right = NULL;
return middle;
}
}

typedef ListNode TreeNode ;

TreeNode* convert(ListNode*& head, int n)
{
       if (n==0) return NULL;
       TreeNode* leftChild = convert(head, n/2);
       TreeNode* root = head;
        head = head->right;
        root->right = convert(head, n-n/2-1);
        root->left = leftChild;
        return root;
        
}
TreeNode* convert(ListNode* head)
{
           int n = countNodes(head);
           return convert(head, n);
}

typedef ListNode TreeNode ;

TreeNode* convert(ListNode*& head, int n)
{
       if (n==0) return NULL;
       TreeNode* leftChild = convert(head, n/2);
       TreeNode* root = head;
        head = head->right;
        root->right = convert(head, n-n/2-1);
        root->left = leftChild;
        return root;
        
}
TreeNode* convert(ListNode* head)
{
           int n = countNodes(head);
           return convert(head, n);
}