Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Convert Sorted List to BST

Convert Sorted List to BST

Master this topic with zero to advance depth.

Convert Sorted List to BST

Convert a sorted linked list to a height-balanced BST.

Visual Representation

List: -10 -> -3 -> 0 -> 5 -> 9 Root is 0.
Medium
Approach 1

Level I: Brute Force (Convert to Array)

Intuition

Convert the linked list into an array. Then, use a standard recursive algorithm to convert the sorted array into a height-balanced BST by picking the middle element as the root.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: -10, -3, 0, 5, 9. Array: [-10, -3, 0, 5, 9].

  1. Root = 0.
  2. Left = [-10, -3].
  3. Right = [5, 9].
java
private List<Integer> values = new ArrayList<>();
public TreeNode sortedListToBST(ListNode head) {
    while (head != null) { values.add(head.val); head = head.next; }
    return buildBST(0, values.size() - 1);
}
private TreeNode buildBST(int left, int right) {
    if (left > right) return null;
    int mid = (left + right) / 2;
    TreeNode root = new TreeNode(values.get(mid));
    root.left = buildBST(left, mid - 1);
    root.right = buildBST(mid + 1, right);
    return root;
}
Approach 2

Level III: Recursive (Middle find)

Intuition

Use slow/fast pointers to find the middle (root), split, and recurse.

⏱ O(N log N)💾 O(log N)
java
public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode prev = null, slow = head, fast = head;
    while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; }
    prev.next = null;
    TreeNode root = new TreeNode(slow.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);
    return root;
}
← Previous QuestionRotate List
Next Question →Binary Search