How hard is LeetCode 109. Convert Sorted List to Binary Search Tree?

LeetCode 109. Convert Sorted List to Binary Search Tree is rated Medium on LeetCode.

What is the time complexity of LeetCode 109. Convert Sorted List to Binary Search Tree?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 109. Convert Sorted List to Binary Search Tree?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 109. Convert Sorted List to Binary Search Tree cover?

LeetCode 109. Convert Sorted List to Binary Search Tree is tagged Tree, Binary Search Tree, Linked List, Divide and Conquer and Binary Tree on LeetCode.

Convert Sorted List to Binary Search Tree — LeetCode 109 Python Solution

MediumTreeBinary Search TreeLinked ListDivide and ConquerBinary Tree

Problem: #109
Pattern: Linked List
Reading time: 4 min
Source: leetcode.com

The problem

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Python solution

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def dfs(i: int, j: int) -> Optional[TreeNode]:
            if i > j:
                return None
            mid = (i + j) >> 1
            l, r = dfs(i, mid - 1), dfs(mid + 1, j)
            return TreeNode(nums[mid], l, r)

        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        return dfs(0, len(nums) - 1)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 109. Convert Sorted List to Binary Search Tree is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 109. Convert Sorted List to Binary Search Tree?: LeetCode 109. Convert Sorted List to Binary Search Tree is rated Medium on LeetCode.
What is the time complexity of LeetCode 109. Convert Sorted List to Binary Search Tree?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 109. Convert Sorted List to Binary Search Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 109. Convert Sorted List to Binary Search Tree cover?: LeetCode 109. Convert Sorted List to Binary Search Tree is tagged Tree, Binary Search Tree, Linked List, Divide and Conquer and Binary Tree on LeetCode.