# 8. 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:**

![](https://assets.leetcode.com/uploads/2020/08/17/linked.jpg)

```
Input: head = [-10,-3,0,5,9]
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]
```

## Solution: (Using Recursion)

**Finding the middle of linked list and creating tree**

```cpp
class Solution
{
public:
    ListNode *findMid(ListNode *head)
    {
        if (head == NULL)
        {
            return head;
        }

        ListNode *p = head;
        ListNode *q = head;
        ListNode *temp = NULL;

        while (p && p->next)
        {
            temp = q;
            q = q->next;
            p = p->next->next;
        }

        if (temp)
        {
            temp->next = NULL;
        }

        return q;
    }

    TreeNode *createBst(ListNode *head)
    {

        if (head == NULL)
        {
            return NULL;
        }

        TreeNode *temp = new TreeNode;

        if (head->next == NULL)
        {
            temp->val = head->val;
            temp->left = NULL;
            temp->right = NULL;
            return temp;
        }

        ListNode *mid = findMid(head);
        temp->val = mid->val;
        temp->left = createBst(head);
        temp->right = createBst(mid->next);

        return temp;
    }

    TreeNode *sortedListToBST(ListNode *head)
    {
        return createBst(head);
    }
};
```

**Time Complexity: O(N logN)**\
**Space Complexity: O(logN)**
