# Convert Sorted List To Binary Search Tree Problem

## Description

LeetCode Problem 109.

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:

``````1
2
3
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:

``````1
2
Output: []
``````

Example 3:

``````1
2
Output: 
``````

Example 4:

``````1
2
Output: [3,1]
``````

Constraints:

• The number of nodes in head is in the range [0, 2 * 10^4].
• -10^5 <= Node.val <= 10^5

## Sample C++ Code

``````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
class Solution {
public:
}

private:
TreeNode *sortedListToBST(ListNode *head, ListNode *tail) {
return NULL;
if( head->next == tail ) {
TreeNode *root = new TreeNode( head->val );
return root;
}
while( temp != tail && temp->next != tail ) {
mid = mid->next;
temp = temp->next->next;
}
TreeNode *root = new TreeNode( mid->val );
root->left = sortedListToBST( head, mid );
root->right = sortedListToBST( mid->next, tail );
return root;
}
};
``````