Convert Sorted List to Binary Search Tree

medium linked list divide and conquer bst

Problem

Given a sorted singly linked list, build a height-balanced BST. The list's middle becomes the root; the left half becomes the left subtree and the right half becomes the right subtree.

Inputhead = -10 → -3 → 0 → 5 → 9

Outputbalanced BST rooted at 0

Use slow/fast to find the middle of each sublist in O(n) per level → O(n log n) total.

sorted values (comma-separated)

def sortedListToBST(head):
    def build(head, tail):
        if head is tail: return None
        slow = fast = head
        while fast is not tail and fast.next is not tail:
            slow = slow.next
            fast = fast.next.next
        node = TreeNode(slow.val)
        node.left = build(head, slow)
        node.right = build(slow.next, tail)
        return node
    return build(head, None)

function sortedListToBST(head) {
  function build(h, tail) {
    if (h === tail) return null;
    let slow = h, fast = h;
    while (fast !== tail && fast.next !== tail) {
      slow = slow.next;
      fast = fast.next.next;
    }
    const node = new TreeNode(slow.val);
    node.left = build(h, slow);
    node.right = build(slow.next, tail);
    return node;
  }
  return build(head, null);
}

class Solution {
    public TreeNode sortedListToBST(ListNode head) { return build(head, null); }
    TreeNode build(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode node = new TreeNode(slow.val);
        node.left = build(head, slow);
        node.right = build(slow.next, tail);
        return node;
    }
}

class Solution {
public:
    TreeNode* build(ListNode* head, ListNode* tail) {
        if (head == tail) return nullptr;
        ListNode* slow = head; ListNode* fast = head;
        while (fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode* node = new TreeNode(slow->val);
        node->left = build(head, slow);
        node->right = build(slow->next, tail);
        return node;
    }
    TreeNode* sortedListToBST(ListNode* head) { return build(head, nullptr); }
};

Explanation

A balanced BST puts a "middle" value at the root so the smaller values fall left and the larger ones fall right. Since the list is already sorted, the natural choice for each root is the middle node of the current sublist, applied recursively.

To find the middle without knowing the length, we use the classic slow/fast pointer trick: fast moves two steps for every one step of slow, so when fast reaches the end, slow sits at the middle.

That middle node becomes the tree root. We then recurse on the part before slow to build the left subtree and the part after slow for the right subtree. The recursion uses a head/tail range so each sublist is just a slice of the original list, with the base case head is tail returning None.

Example: -10 → -3 → 0 → 5 → 9. The middle is 0, so it is the root. The left half -10, -3 builds the left subtree and the right half 5, 9 builds the right, giving a height-balanced tree.

Splitting always picks the middle, so the tree stays balanced. Finding middles costs O(n) per level over O(log n) levels, for O(n log n) total.

Time: O(n log n) Space: O(log n) recursion