Convert Sorted Linked List to BST

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

Question#

Given the head of singly linked list which is also sorted, convert it to a height-balanced BST.

Height balanced: depth of the two subtrees of every node never differ by more than 1.

Implementation#

In this solution, we convert the linked list into an array. We find the middle of the array and make it the root of the BST. We get the middle of the subarray to the left of mid node and make it the left child. Similarly, we get the middle of the subarray to the right of the mid node and make it the right child.

We do this in a recursive manner till we complete the BST.

class Solution:
def sortedArrayToBST(self, arr):
if(len(arr) == 0):
return None
elif(len(arr) == 1):
return TreeNode(arr[0])
mid = len(arr) // 2
middle = TreeNode(arr[mid])
middle.left = self.sortedArrayToBST(arr[0:mid])
middle.right = self.sortedArrayToBST(arr[mid + 1:])
return middle
def sortedListToBST(self, head: ListNode) -> TreeNode:
curr = head
arr = []
while curr:
arr.append(curr.val)
curr = curr.next
return self.sortedArrayToBST(arr)

The second approach without conversion to an array is to write an auxillary function to get the middle of the linked list. Each time, we need to break the linkage between the previous to middle node and the middle node. We recurse the method in a similar fashion to above.