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

# BST & LinkedList - Convert Sorted List to Binary Search Tree

LeetCode 109 - classic question of combining linkedlist and tree

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return
        if not head.next:
            return TreeNode(head.val)
        
        def findMid(head):
            t = r = head
            # 1 -> 2 -> 3 -> 4 -> None
            #           t
            #                      r
            while r and r.next :
                prev  =  t
                t = t.next
                r = r.next.next
            prev.next = None
            return t
            
            
        mid = findMid(head)
        root = TreeNode(mid.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(mid.next)
        
        return root
```