# Given a sorted linkedlist, convert to BST(binary search tree)

For example, given a sorted linkedlist `1->2->3-4->5->6->7`, output should be:
```     4
/  \
2     6
/ \   / \
1   3 5   7
```
The sorted list represents the inorder traversal of a tree. The middle element of an array represents to root of the tree. The elements on left of the middle element are left children of the tree and elements on the right of the middle element are right children of the tree. ` 1->2->3 <- 4 -> 5->6->7` Now in `[1,2,3] ` The middle element is left child of parent node 4 and 1,3 are left and right child respectively. If we follow this pattern, then we can write a program where once the middle element is found, we recursively break the sub arrays in the nodes and attach the left child and right child respectively. Finding the middle element in a linked list requires O(n) time.
``````  public class ArrayToTree {
return null;
}

int size = 0;
while(first != null){
first = first.next;
size ++;
}

return inorder(0, size - 1);
}

public TreeNode inorder(int start, int end){
if(start > end){
return null;
}

int mid = start + (end - start) / 2;
TreeNode left = inorderHelper(start, mid - 1);

TreeNode root = new TreeNode(node.val);
root.left = left;
node = node.next;

TreeNode right = inorderHelper(mid + 1, end);
root.right = right;
return root;
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}
}``````