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]

• Arya Singh: Don't you think that adding tuple packing & unpacking would increase complexity for this code although it's nice to remove redundant beg and end. Does tuple unpacking follows Pythonic code style?
• Toby Speight: Not sure - other reviewers might have opinions. We could still have a hybrid of your original (updating self.head) and this version (single node_count) which would then only need a single return value. I did both just to show alternative approaches.