Code Review: (sorted) linked list to a BST.

main.py

import time


class ListNode():
    def __init__(self, datum):
        self.datum = datum
        self.next = None


class LinkedList():
    def __init__(self):
        self.head = None
        self.tail = None

    # We can always get rid of the self.tail reference, but it
    # helps to speed up the append operation:
    def append(self, datum):
        node = ListNode(datum)
        if self.head:
            self.tail.next = node
            self.tail = node
        else:
            self.head = self.tail = node


class TreeNode():
    def __init__(self, datum):
        self.datum = datum
        self.left  = None
        self.right = None

    def __str__(self):
        return f"[{self.datum}, left {self.left} | right {self.right}]"


def convert_linked_list_to_bst(linked_list: LinkedList):
    # Convert the input linked list to an array:
    array = []
    current_node = linked_list.head

    while current_node:
        array.append(current_node.datum)
        current_node = current_node.next

    # In the CR post, all (as of now) do not produce a true BST
    # unless the input linked list is sorted. Uncomment the below
    # in order to always producing BSTs with complexity
    # boost O(N) -> O(N log N):
    # array.sort()

    def convert_impl(array, lo, hi):
        if hi - lo < 1:
            return None

        mid = lo + (hi - lo) // 2
        root = TreeNode(array[mid])
        root.left = convert_impl(array, lo, mid)
        root.right = convert_impl(array, mid + 1, hi)
        return root

    # Spawn the tree construction:
    return convert_impl(array, 0, len(array))


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.datum)
    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)


def list_length(node: ListNode):
    sz = 0
    current = node

    while current:
        sz += 1
        current = current.next

    return sz


def sortedListToBST(linked_list: LinkedList) -> TreeNode:
    return make_subtree(linked_list.head, list_length(linked_list.head))[0]


def to_linked_list(lst):
    r = LinkedList()

    for i in lst:
        r.append(i)

    return r


def main():
    small_demo()

    lst = [i for i in range(0, 10000000)] # ten million elements
    lst = to_linked_list(lst)# ten million

    t = time.perf_counter()
    convert_linked_list_to_bst(lst)
    d = (time.perf_counter() - t) * 1000

    print(f"coderodde's version in {d:.3f} milliseconds.")

    t = time.perf_counter()
    sortedListToBST(lst)
    d = (time.perf_counter() - t) * 1000

    print(f"Toby Speight's version in {d:.3f} milliseconds.")


def small_demo():
    list = LinkedList()
    list.append(1)
    list.append(2)
    list.append(3)
    list.append(4)
    list.append(5)

    tree = convert_linked_list_to_bst(list)
    print(tree)
    print(sortedListToBST(list))


if __name__ == "__main__":
    main()