> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/convert-sorted-list-to-binary-search-tree.md).

# Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

> **A height balanced BST :** a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 

**Example :**

```

Given A : 1 -> 2 -> 3
A height balanced BST  :

      2
    /   \
   1     3
```

```java
public class Solution {
    public int length(ListNode a) {
        int len = 0;
        while (a != null) {
            len++;
            a = a.next;
        }
        return len;
    }

    public TreeNode helper(ListNode a, int len) {
        if (len == 0)
            return null;
        int mid = (len + 1) / 2;
        ListNode t = a;
        for (int i = 1; i < mid; i++)
            t = t.next;
        TreeNode root = new TreeNode(t.val);
        root.left = helper(a, mid - 1);
        root.right = helper(t.next, len - mid);
        return root;
    }

    public TreeNode sortedListToBST(ListNode a) {
        int len = length(a);
        return helper(a, len);
    }
}
```