Convert Sorted List to Binary Search Tree

22 Jun 2019

leetcode algorithm binary search tree linked list

Problem description

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution

We need to find the middle of the sorted list and recursively construct the left subtree and right subtree from the left half list and right half list.
To find the middle of the sorted list, we use a fast pointer and a slow point, in which the fast pointer move twice fast as the slow pointer.

Below is my python implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if head == None:
            return None
        if head.next == None:
            return TreeNode(head.val)
        fast = head
        slow = head
        prev = None
        while fast and fast.next:
            fast = fast.next
            fast = fast.next
            prev = slow
            slow = slow.next
        #now recursively call first half linked list and last half linked list
        if prev:
            prev.next = None
        left = self.sortedListToBST(head)
        right = self.sortedListToBST(slow.next)
        root = TreeNode(slow.val)
        root.left = left
        root.right = right
        return root
        