Leetcode (Python): Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:

In order to avoid traversing an element more than once we keep a ListNode that its next element indicates which node is one that we have to process.

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a list node
    # @return a tree node
    def sortedListToBST(self, head):
        count = 0
        temp = head
        while temp != None:
            temp = temp.next
            count +=1
        return self.sortedListToBST2(head, count, ListNode(0))
    
    def sortedListToBST2(self, head, numberElements, next):
        if numberElements == 0:
            next.next = head
            return None
        leftTree = self.sortedListToBST2(head, numberElements//2, next)
        root = TreeNode(next.next.val)
        next.next = next.next.next
        rightTree = self.sortedListToBST2(next.next, numberElements-1-numberElements//2, next)
        root.left = leftTree
        root.right = rightTree
        return root