Convert Sorted List to Binary Search Tree

lcpy gen -n 109   # by problem number
lcpy gen -s convert_sorted_list_to_binary_search_tree   # by problem name

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.

Input: head = []
Output: []

from leetcode_py import ListNode, TreeNode


class Solution:
    # Time: O(n) - each list node is visited once, in the same order the
    # in-order traversal consumes them.
    # Space: O(log n) - recursion depth equals the tree height.
    def sorted_list_to_bst(self, head: ListNode[int] | None) -> TreeNode[int] | None:
        size = 0
        node = head
        while node is not None:
            size += 1
            node = node.next

        cursor = head

        def build(lo: int, hi: int) -> TreeNode[int] | None:
            nonlocal cursor
            if lo > hi:
                return None
            mid = (lo + hi) // 2
            left = build(lo, mid - 1)
            cur = cursor
            assert cur is not None
            cursor = cur.next
            return TreeNode(cur.val, left, build(mid + 1, hi))

        return build(0, size - 1)