Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def find_middle(start, end):
            slow = fast = start
            while fast != end and fast.next != end:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        def convert(start, end):
            if start == end:
                return None
            mid = find_middle(start, end)
            node = TreeNode(mid.val)
            node.left = convert(start, mid)
            node.right = convert(mid.next, end)
            return node
        
        return convert(head, None)
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return convert(head, null);
    }
    private TreeNode convert(ListNode start, ListNode end) {
        if (start == end) return null;
        ListNode mid = findMiddle(start, end);
        TreeNode node = new TreeNode(mid.val);
        node.left = convert(start, mid);
        node.right = convert(mid.next, end);
        return node;
    }
    private ListNode findMiddle(ListNode start, ListNode end) {
        ListNode slow = start;
        ListNode fast = start;
        while (fast != end && fast.next != end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    function findMiddle(start, end) {
        let slow = start, fast = start;
        while (fast !== end && fast.next !== end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    function convert(start, end) {
        if (start === end) return null;
        let mid = findMiddle(start, end);
        let node = new TreeNode(mid.val);
        node.left = convert(start, mid);
        node.right = convert(mid.next, end);
        return node;
    }
    return convert(head, null);
};
      

Problem Description

Given the head of a singly linked list head where the elements are sorted in ascending order, your task is to convert it into a height-balanced binary search tree (BST).
A height-balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

• Each element in the linked list must be used exactly once in the BST.
• The BST must be height-balanced.
• There is only one valid solution for a given input.
• You may not modify or reuse the linked list nodes as tree nodes; you must create new tree nodes.

Thought Process

The main challenge is to convert a sorted sequence (in the form of a singly linked list) into a balanced BST. If the input were an array, we could easily pick the middle element as the root and recursively build the left and right subtrees. However, since the input is a singly linked list, we cannot access the middle element in constant time.

A brute-force approach would be to convert the list into an array, then use the array-to-BST method. But this uses extra space. To optimize, we look for a way to find the middle of the list in-place (using slow and fast pointers), allowing us to recursively construct the BST without extra storage.

The key insight is to use the slow and fast pointer technique to find the middle node of any sublist, which will serve as the root of the (sub)tree. We then recursively build the left and right subtrees from the left and right parts of the list.

Solution Approach

• Step 1: Find the Middle Node
  • Use two pointers: slow and fast.
  • slow moves one step at a time, fast moves two steps.
  • When fast reaches the end, slow will be at the middle node.
• Step 2: Recursive BST Construction
  • Recursively build the left subtree from the left part of the list (before middle).
  • The middle node becomes the root.
  • Recursively build the right subtree from the right part of the list (after middle).
• Step 3: Base Case
  • If the start of the list equals the end, return null (no nodes to process).
• Step 4: Recursion Boundaries
  • We pass start and end pointers to delimit the current sublist.
  • For the left subtree, use start to mid.
  • For the right subtree, use mid.next to end.
• Why This Works
  • Each subtree is constructed from a sublist, always picking the middle node as root, ensuring balance.
  • No extra space is used except for recursion stack and the tree itself.

Example Walkthrough

Input: head = [-10, -3, 0, 5, 9]

1. First Call:
   • Find middle: 0 (slow/fast pointer technique)
   • 0 becomes root
2. Left Subtree:
   • Sublist: [-10, -3]
   • Middle: -10 (slow at -10, fast at -3)
   • -10 becomes left child
   • Right of -10: -3 (becomes right child of -10)
3. Right Subtree:
   • Sublist: [5, 9]
   • Middle: 9 (slow at 5, fast at 9)
   • 9 becomes right child
   • Left of 9: 5 (becomes left child of 9)
4. Resulting BST:

   •               0
                  / \
                -10  9
                  \  /
                 -3 5
               

Time and Space Complexity

• Brute-force approach (convert to array):
  • Time: O(N) to convert list to array + O(N) to build BST = O(N)
  • Space: O(N) for the array
• Optimized in-place approach (slow/fast pointer):
  • Time: O(N log N) — Each level of recursion does O(N) work to find the middle, and there are O(log N) levels
  • Space: O(log N) for recursion stack (height of tree)
• Why not O(N)?
  • Because finding the middle takes O(N) time for each recursive call, and the depth is O(log N)

Summary

To convert a sorted singly linked list to a height-balanced BST, we use the slow/fast pointer technique to find the middle node, recursively building the tree by always choosing the middle as the root. This ensures the BST is balanced. The approach is elegant because it avoids extra space and leverages linked list traversal, though it does have O(N log N) time complexity. Understanding this recursive, divide-and-conquer method is key to tackling many similar problems involving sorted data and balanced trees.