Convert Sorted List to Balanced Binary Search Tree

When we see “balanced,” it means we need to use the middle of the list as the root each time we build our tree.

The key parts:

Find the middle of a list -> fast and slow pointers
Split the list -> make sure each recursive call can find the middle of its sublists correctly. We need to track the previous node of the slow pointer so we can cut the list.

Fast and slow pointer template:

ListNode *fast, *slow;
fast = slow = head;
while(fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow points to the middle of the list

TreeNode* sortedListToBST(ListNode* head) {
    if (head == NULL) return NULL;
    if (head->next == NULL) return new TreeNode(head->val);

    ListNode *fast, *slow, *prev;
    fast = slow = head;
    while(fast && fast->next) {
        // Track the previous node
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    // Cut the list
    prev->next = NULL;

    TreeNode* root = new TreeNode(slow->val);
    // Build BST from left and right halves
    TreeNode* left = sortedListToBST(head);
    TreeNode* right = sortedListToBST(slow->next);
    root->left = left;
    root->right = right;
    return root;
}

#recursion #divide-and-conquer #bst #tree

Connecting Nodes at the Same Level Count Primes