Convert sorted list to BST

Question

I am working on a Daily Coding Challenge to convert a sorted singly-linked list into a binary search tree.

We are given the head of the list; the definitions of ListNode and TreeNode are provided by the challenge.

Below is my code in Python 3.11. Code works fine and produces desired output.

Please can anyone review it in terms of readability and any optimization that can be made.

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:        
        def helper(beg, end):
            if beg > end: return None
            mid = (beg + end)//2
            left = helper(beg, mid - 1)
            root = TreeNode(self.head.val)
            self.head = self.head.next
            root.left = left
            root.right = helper(mid + 1, end)
            return root
        
        self.head, copy, n = head, head, 0
        while copy:
            copy = copy.next
            n += 1
            
        return helper(0, n-1)

Answer 1

It took me a long time to follow the logic here. That could be greatly improved by adding comments to the code.

The name helper isn't very informative; I think we could make a better name for it.

The loop that measures the input list length could usefully be extracted as a helper function. That's an opportunity to give it (and n) a meaningful name:

def list_length(seq: ListNode) -> int:
    n = 0
    while seq:
        seq = seq.next
        n += 1
    return n

I don't think we really need both beg and end as arguments to helper() - merely the number of nodes to consume from the beginning of the list. That would make it look something like this (returning the new subtree root and the remaining unconsumed list tail):

def make_subtree(list_head, node_count):
    if not node_count:
        return (None, list_head)
    # split into half to balance the tree
    mid = node_count // 2
    # left-hand sub-subtree
    left, list_head = make_subtree(list_head, mid)
    # subtree root node
    root = TreeNode(list_head.val)
    list_head = list_head.next
    root.left = left
    # right-hand sub-subtree
    root.right, list_head = make_subtree(list_head, node_count - mid - 1)
    return (root, list_head)

Then the main function becomes simply:

def sortedListToBST(self, head: ListNode) -> TreeNode:
    return make_subtree(head, list_length(head))[0]