Problem statement

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Solution

There are solutions with different time/space complexities.

  1. We can just transform everything to array and then create bst, in O(n) time and O(n) space.
  2. Or we can not create array, but then each time we need to find middle, and time will be O(n log n).

Imagine now, that we can reuse nodes of our linked list to create nodes of bst. This is not the case in this problem, but if it was the case than we can have space complexity smaller than O(n). The main complexity in idea 2 is that we always need to find the middle element in list, which is quite heavy: we need to traverse all (or half) of the list. Let us use function helper(beg, end), with:

  1. (beg, end) are indexes in original linked list we want to traverse and create BST from these elements.
  2. Output will be the root of BST
  3. We also keep one more piece of information: self.head: global variable, which will help us to have quick access to desired elements: on step i in inorder traversal it will point to i-th element in linked list. More precisely when we run helper(beg, end), after execution of this code, self.head will point to the element with index end + 1. This is invariant of our helper functioun.

Now, function will look like this:

  1. Check if beg > end and if it is the case, we out of nodes, we return None.
  2. Find mid element as (beg + end)//2.
  3. Run our helper function recursively: helper(beg, mid - 1). Note where our self.head is now. It is changed after we run this funtion and now points at element with index mid.
  4. Create root: we use self.head for this.
  5. Move self.head one step to the right.
  6. Now, it is time to attach left subtree to our root.
  7. Finally, attach right subtree: helper(mid + 1, end) to our root. Note howe self.head changed after this: it will point at element with index end + 1. So, we proved, that our invariant holds.
  8. Return root.

Complexity

Time complexity is O(n): we traverse every node only once. Space complexity is also O(n), because we need to create object with n elements in the end. However why this is better than creating array, is because if we allowed to modify elements of the linked list to make them directly elements of BST, then space complexity would have been O(log n).

Code

class Solution:
    def sortedListToBST(self, head):
        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)