# 109 Convert Sorted List to Binary Search Tree

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

For this problem, 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 1:

``````-10 -> -3 -> 0 -> 5 -> 9

0                   0
/   \               /   \
-10    5      or    -3     9
\     \           /     /
-3     9        -10    5

Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5],
which represents the shown height balanced BST.
``````

Example 2:

``````Input: head = []
Output: []
``````

Example 3:

``````Input: head = [0]
Output: [0]
``````

Example 4:

``````Input: head = [1,3]
Output: [3,1]
``````

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].
• -105 <= Node.val <= 105
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 `````` ``````# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findSize(self, head): ptr = head c = 0 while ptr: ptr = ptr.next c += 1 return c def sortedListToBST(self, head: ListNode) -> TreeNode: # Get the size of the linked list first size = self.findSize(head) # Recursively form a BST out of linked list from l --> r def convert(l, r): nonlocal head # Invalid case if l > r: return None mid = (l + r) // 2 # First step of simulated inorder traversal. Recursively form # the left half left = convert(l, mid - 1) # Once left half is traversed, process the current node node = TreeNode(head.val) node.left = left # Maintain the invariance mentioned in the algorithm head = head.next # Recurse on the right hand side and form BST out of them node.right = convert(mid + 1, r) return node return convert(0, size - 1)``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 `````` ``````/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findSize(head *ListNode) int { c := 0 for head != nil { head = head.Next c++ } return c } var list *ListNode func convert(left, right int) *TreeNode { if left > right { return nil } mid := (left + right) / 2 newLeft := convert(left, mid-1) node := &TreeNode{list.Val, newLeft, nil} list = list.Next node.Right = convert(mid+1, right) return node } func sortedListToBST(head *ListNode) *TreeNode { list = head size := findSize(head) return convert(0, size-1) }``````