How do you solve Convert Sorted List to Binary Search Tree on LeetCode?

Convert Sorted List to Binary Search Tree (LeetCode #109) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(log n) space complexity. Key insight: Using the middle element of the sorted list as the root ensures balance.

What is the brute force solution for Convert Sorted List to Binary Search Tree?

The brute force approach for Convert Sorted List to Binary Search Tree is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves converting the linked list to an array, then recursively building the binary search tree (BST) from the array. This is straightforward but inefficient due to the extra space and time required for conversion. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Convert Sorted List to Binary Search Tree?

Explain your thought process clearly while coding. Discuss the time and space complexities of your approach. Be prepared to optimize your solution if asked.

What are common mistakes when solving Convert Sorted List to Binary Search Tree?

Not considering the base case for recursion properly. Forgetting to update the head pointer during recursion.

#109

Convert Sorted List to Binary Search Tree

Medium

Linked ListDivide and ConquerTreeBinary Search TreeBinary TreeDivide and ConquerRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(log n)

💡

Intuition

Time O(n)Space O(log n)

The optimal approach uses a recursive function to build the BST directly from the linked list without converting it to an array. This is more efficient as it reduces space usage and avoids the overhead of array manipulation.

⚙️

Algorithm

3 steps

1Step 1: Count the number of nodes in the linked list.
2Step 2: Recursively build the BST by selecting the middle node as the root, using in-order traversal.
3Step 3: For each recursive call, adjust the head pointer to move through the linked list.

solution.py35 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class TreeNode:
8    def __init__(self, val=0, left=None, right=None):
9        self.val = val
10        self.left = left
11        self.right = right
12
13class Solution:
14    def sortedListToBST(self, head: ListNode) -> TreeNode:
15        def findSize(head):
16            size = 0
17            while head:
18                size += 1
19                head = head.next
20            return size
21
22        def convertListToBST(left, right):
23            nonlocal head
24            if left > right:
25                return None
26            mid = (left + right) // 2
27            left_child = convertListToBST(left, mid - 1)
28            node = TreeNode(head.val)
29            node.left = left_child
30            head = head.next
31            node.right = convertListToBST(mid + 1, right)
32            return node
33
34        size = findSize(head)
35        return convertListToBST(0, size - 1)

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once to build the BST. The space complexity is O(log n) due to the recursion stack used during the recursive calls.

1Using the middle element of the sorted list as the root ensures balance.
2Recursive tree construction allows direct manipulation of the linked list.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.