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)

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]
  • \$\begingroup\$ 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? \$\endgroup\$
    – Arya Singh
    Mar 13 at 16:42
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 13 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.