# Convert Sorted Linked list to balanced BST

In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list.

Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1).

Approach :
i. Get the middle of the linked list and make the middle element as root of the tree.
ii. Recursively do the same for left and right half of linked list.

```struct list
{
int value;
struct list* next;
};

struct node
{
int value;
struct node* left;
struct node* right;
};

struct node* newNode(int value);

{
int count = 0;
{
count++;
}
return count;
}

struct node* newNode(int value)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->value = value;
newnode->left = NULL;
newnode->right = NULL;

return newnode;
}
{
}

{
if (start > end)
return NULL;

int mid = start+(end-start)/2;
struct list * temp = *head;
int i = 0;
while(i<mid && temp->next!=NULL)
{
temp = temp->next;
i++;
}
struct node *root = newNode(temp->value);
return root;
}
```

Time Complexity : O(NlogN)

Better Solution (bottom -up manner) : In this approach,We create the tree from bottom to root. This enables us to insert nodes in the tree in the same order as they appear in the list. So we don’t need to find the middle element as we are able to traverse list while inserting nodes to the tree. We first count the total number of nodes in the list.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). While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.

```struct node* linkedListToBST(struct list *head)
{
}

{
if (start > end)
return NULL;

int mid = start+(end-start)/2;

root->left = leftChild;

return root;
}
```

### 5 Thoughts on “Convert Sorted Linked list to balanced BST”

1. I think the 2nd approach won’t give the expected output.Below is my observation:
The head remain same for all the recursive call for left child hence the root of the tree would be the first node of the linked list instead of the mid node of the list.
E.g 2->4->6->8->10->12->14
The root of the tree would be 2 and left would also be 2.

2. 1st approach also wouldn’t work while constructing right subtree.
There is no need to use ** as we are not modifying list.

• Raghvendra Mishra on June 14, 2016 at 6:08 pm said:

withroot->right = linkedListToBSTUtil(temp->next, mid+1,end); should work

node *leftsubtree = NULL;
while (t) {
node *nnode = new node(t->val);
t->left = leftsubtree;
t = t->next;
if (t) {
node *rt = new node(t->val);
t->right = rt;
}
leftsubtree = t;
t = t->next;
}
return leftsubtree;
}

Complexity: O(n) no count or additional space is needed to be kept

node *leftsubtree = NULL;
while (t) {
node *nnode = new node(t->val);
nnode->left = leftsubtree;
t = t->next;
if (t) {
node *rt = new node(t->val);
nnode->right = rt;
}
leftsubtree = nnode;
t = t->next;
}
return leftsubtree;
}

Complexity: O(n) no count or additional space is needed to be kept