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:

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

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)