#109

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Convert Sorted List to Binary Search Tree

Convert a sorted singly linked list into a height-balanced BST using pointer manipulation and divide-and-conquer recursion efficiently in interviews.

linked list divide and conquer tree binary search tree binary tree

Problem Statement

You are given the head of a singly linked list where elements are sorted in ascending order. Your task is to convert this list into a height-balanced binary search tree. The goal is to ensure that the depth of the two subtrees of every node never differs by more than one while preserving the sorted order in the BST structure. Proper pointer manipulation is required to avoid unnecessary copying of list segments.

For example, given head = [-10,-3,0,5,9], one valid height-balanced BST is [0,-3,9,-10,null,5]. Another edge case is an empty list, which should return an empty BST. Constraints include up to 20,000 nodes and node values ranging from -105 to 105. Focus on linked-list traversal patterns and divide-and-conquer recursion for efficient implementation.

Examples

Example 1

Input: head = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]

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

Example 2

Input: head = []

Output: []

Example details omitted.

Constraints

The number of nodes in head is in the range [0, 2 * 104].
-105 <= Node.val <= 105

Solution Approach

Find Middle Node Using Slow-Fast Pointers

To construct the BST, locate the middle node of the linked list, which becomes the root. Use a slow and fast pointer to traverse: the fast pointer moves twice as fast as slow. When fast reaches the end, slow points to the middle. Disconnect the left sublist to allow recursive BST construction. This pointer-based approach avoids creating new lists and reduces overhead, ensuring the tree is height-balanced while respecting the original list nodes.

Recursive Divide-and-Conquer Construction

After identifying the middle node as the root, recursively apply the same strategy to the left and right sublists. Each recursive call finds the middle of its segment to serve as the subtree root. Continue until the sublist is empty, which returns null. This divide-and-conquer strategy ensures a balanced BST. Proper pointer handling is critical to prevent incorrect connections or cycles in the tree structure, particularly when lists contain few nodes or duplicates.

Inorder Simulation Without Extra Space

An alternative technique simulates inorder traversal to construct the BST directly while iterating through the list once. Maintain a global pointer to the current list node and recursively construct left subtree, assign current node as root, then move to the next node and build the right subtree. This approach avoids splitting the list repeatedly, achieves O(n) time, and uses O(log n) recursion stack space. Correct pointer movement ensures nodes appear in the correct BST order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach: splitting lists recursively is O(n log n), whereas inorder simulation achieves O(n). Space complexity is O(log n) due to recursion stack in a balanced BST. Using pointer manipulation avoids extra arrays, reducing overhead compared to naive list copying, making this solution memory-efficient while maintaining height balance.

What Interviewers Usually Probe

Do you correctly find the middle node without extra list creation?
Can you maintain pointer integrity while recursively constructing left and right subtrees?
Will you handle empty and single-node lists without causing null pointer errors?

Common Pitfalls or Variants

Common pitfalls

Failing to disconnect the left sublist causes cycles or incorrect subtree connections.
Using list slicing instead of pointer manipulation increases space and breaks the O(n) expectation.
Incorrect middle selection in even-length lists can unbalance the BST or violate height-balance requirement.

Follow-up variants

Convert Sorted Array to BST (array-based version with direct index access).
Balanced BST to Sorted Linked List (reverse pattern requiring inorder traversal).
Convert Sorted Circular Linked List to BST (requires handling circular pointer traversal).

FAQ

How do I find the middle node in a sorted linked list for BST conversion?

Use the slow and fast pointer technique where slow moves one step and fast moves two steps; slow will point to the middle node when fast reaches the end.

What happens if the list has an even number of nodes?

Choose the second of the two middle nodes to maintain height balance consistently, preventing left-heavy or right-heavy trees in recursive construction.

Can I use extra arrays instead of pointer manipulation?

While possible, using extra arrays increases space complexity and violates the efficient pointer manipulation pattern expected for this problem, reducing memory efficiency.

How does GhostInterview handle empty lists?

It recognizes an empty list and returns a null root, ensuring recursive calls terminate correctly without null pointer exceptions.

Why is pointer manipulation critical for this problem?

Pointer manipulation avoids copying sublists, preserves original nodes, reduces space usage, and maintains the sorted order and height-balance required for BST correctness.

terminal

Solution

Solution 1: DFS

We first convert the linked list to an array $\textit{nums}$, and then use depth-first search to construct the binary search tree.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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)

Continue Practicing

#108 convert sorted array to binary search tree #106 construct binary tree from inorder and postorder traversal #105 construct binary tree from preorder and inorder traversal