# Convert sorted list to BST

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.

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.left = left
root.right = helper(mid + 1, end)
return root

while copy:
copy = copy.next
n += 1

return helper(0, n-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:
# split into half to balance the tree
mid = node_count // 2
# left-hand sub-subtree
# subtree root node

def sortedListToBST(self, head: ListNode) -> TreeNode:

• 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? Mar 13 at 16:42
• 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. Mar 13 at 17:05