Log inSign up
mediumLeetCodeNot Started

Convert Sorted List to Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Contrast array midpoint partitioning with linked list traversal bottlenecks.
  • Understand why inorder tree construction synchronizes with sequential linked list traversal.
  • Implement the O(N) monotonic head pointer recursion pattern.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted singly linked list to balanced binary search tree.
  • No O(1) random index access available in linked list.
  • Strict height-balance constraint |height(left) - height(right)| <= 1.

Algorithmic Decision Tree:

  • If O(N) auxiliary space is permitted -> Convert list to array, then use array midpoint divide-and-conquer.
  • If O(1) extra space (excluding recursion stack) is required -> Inorder simulation with sequential head pointer advance.

Connected Patterns:

Convert Sorted Array to Binary Search TreeFlatten Binary Tree to Linked ListMiddle of the Linked List

1. Slow & Fast Pointers Midpoint Divide-and-Conquer

Intuition

At each step, use two pointers (slow and fast) to find the midpoint of the current list segment. Create a tree node with slow.val. Disconnect the left half from slow (or pass boundaries), then recursively call the function on the left half and right half (slow.next). Because finding the middle takes O(L) time at each level and there are O(log N) levels, the total time is O(N log N).

When to apply: When understanding the natural extension of the array divide-and-conquer algorithm to linked lists.

Algorithm

  1. Find the middle of the linked list using slow and fast pointers at each recursive level, disconnect or bound the list, and recurse on halves.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode* next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9struct TreeNode {
10 int val;
11 TreeNode* left;
12 TreeNode* right;
13 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14};
15
16class Solution {
17public:
18 TreeNode* sortedListToBST(ListNode* head) {
19 if (!head) return nullptr;
20 if (!head->next) return new TreeNode(head->val);
21
22 ListNode* prev = nullptr;
23 ListNode* slow = head;
24 ListNode* fast = head;
25
26 while (fast && fast->next) {
27 prev = slow;
28 slow = slow->next;
29 fast = fast->next->next;
30 }
31
32 // Disconnect left half
33 if (prev) prev->next = nullptr;
34
35 TreeNode* root = new TreeNode(slow->val);
36 root->left = sortedListToBST(head);
37 root->right = sortedListToBST(slow->next);
38
39 return root;
40 }
41};
42
43int main() {
44 // Construct [-10, -3, 0, 5, 9]
45 ListNode* head = new ListNode(-10);
46 head->next = new ListNode(-3);
47 head->next->next = new ListNode(0);
48 head->next->next->next = new ListNode(5);
49 head->next->next->next->next = new ListNode(9);
50
51 Solution sol;
52 TreeNode* root = sol.sortedListToBST(head);
53 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ", Right: " << root->right->val << ")" << std::endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(log N) stack frames

2. Array Conversion + Midpoint Partitioning

Intuition

Traverse the linked list and append values into an array vals. Then call build(0, vals.length - 1) where mid = (L + R) / 2. root.left = build(L, mid - 1) and root.right = build(mid + 1, R). This achieves strictly O(N) time because indexing an array is O(1).

When to apply: When O(N) auxiliary space is acceptable and maximum implementation speed / simplicity is desired.

Algorithm

  1. Copy all linked list values into an array in O(N) time, then apply standard O(N) array-to-BST midpoint divide-and-conquer.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct ListNode {
5 int val;
6 ListNode* next;
7 ListNode(int x) : val(x), next(nullptr) {}
8};
9
10struct TreeNode {
11 int val;
12 TreeNode* left;
13 TreeNode* right;
14 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
15};
16
17class Solution {
18 TreeNode* build(const std::vector<int>& vals, int l, int r) {
19 if (l > r) return nullptr;
20 int mid = l + (r - l) / 2;
21 TreeNode* root = new TreeNode(vals[mid]);
22 root->left = build(vals, l, mid - 1);
23 root->right = build(vals, mid + 1, r);
24 return root;
25 }
26public:
27 TreeNode* sortedListToBST(ListNode* head) {
28 std::vector<int> vals;
29 while (head) {
30 vals.push_back(head->val);
31 head = head->next;
32 }
33 return build(vals, 0, (int)vals.size() - 1);
34 }
35};
36
37int main() {
38 ListNode* head = new ListNode(-10);
39 head->next = new ListNode(-3);
40 head->next->next = new ListNode(0);
41 head->next->next->next = new ListNode(5);
42 head->next->next->next->next = new ListNode(9);
43
44 Solution sol;
45 TreeNode* root = sol.sortedListToBST(head);
46 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ", Right: " << root->right->val << ")" << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N) auxiliary space

3. Inorder Simulation with Monotonic Head Pointer

Intuition

First, count total nodes N in O(N) time. The inorder traversal of a BST produces elements in strictly ascending sorted order, which matches the order of the linked list exactly. Define build(L, R). When recursing, build the left child with build(L, mid - 1). When the left child returns, the current head pointer in the linked list is guaranteed to point to the exact node for mid! Create the root node with head.val, advance head = head.next, and build the right child with build(mid + 1, R). Attach left and right subtrees and return.

When to apply: Optimal in both time and auxiliary space. Preferred in production and technical interviews.

Algorithm

  1. Count the total number of nodes N, then simulate inorder traversal (Left -> Node -> Right). Advance the head pointer sequentially as nodes are materialized.

Monotonic Inorder Head Pointer Simulation

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Compute count = 5
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
N = 5. Target mid = 2. Recurse left range [0..1].
Decision / next transition
1
Why this step matters

Compute count = 5. Left boundary is 0, right is 4. Left subtree receives range [0..1].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode* next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9struct TreeNode {
10 int val;
11 TreeNode* left;
12 TreeNode* right;
13 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14};
15
16class Solution {
17 ListNode* curr;
18
19 TreeNode* build(int l, int r) {
20 if (l > r) return nullptr;
21
22 int mid = l + (r - l) / 2;
23
24 // 1. Inorder: recursively build left subtree
25 TreeNode* leftChild = build(l, mid - 1);
26
27 // 2. Consume current list node for root
28 TreeNode* root = new TreeNode(curr->val);
29 root->left = leftChild;
30 curr = curr->next;
31
32 // 3. Inorder: recursively build right subtree
33 root->right = build(mid + 1, r);
34
35 return root;
36 }
37public:
38 TreeNode* sortedListToBST(ListNode* head) {
39 int count = 0;
40 ListNode* p = head;
41 while (p) {
42 count++;
43 p = p->next;
44 }
45 curr = head;
46 return build(0, count - 1);
47 }
48};
49
50int main() {
51 ListNode* head = new ListNode(-10);
52 head->next = new ListNode(-3);
53 head->next->next = new ListNode(0);
54 head->next->next->next = new ListNode(5);
55 head->next->next->next->next = new ListNode(9);
56
57 Solution sol;
58 TreeNode* root = sol.sortedListToBST(head);
59 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ", Right: " << root->right->val << ")" << std::endl;
60 return 0;
61}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(log N) recursion call stack

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Slow & Fast Pointers Midpoint Divide-and-ConquerO(N log N)O(log N) stack framesFind the middle of the linked list using slow and fast pointers at each recursive level, disconnect or bound the list, and recurse on halves.O(N log N)
2.Array Conversion + Midpoint PartitioningO(N)O(N) auxiliary spaceCopy all linked list values into an array in O(N) time, then apply standard O(N) array-to-BST midpoint divide-and-conquer.O(N)
3.Inorder Simulation with Monotonic Head PointerOptimalO(N)O(log N) recursion call stackCount the total number of nodes N, then simulate inorder traversal (Left -> Node -> Right). Advance the head pointer sequentially as nodes are materialized.O(N)

Common Pitfalls & Crucial Edge Cases

Advance pointer at the wrong time

Advancing curr = curr.next before recursing into the left child results in completely scrambled tree values.

Mutable pointer scope

In Python/JavaScript, failing to capture curr via closure/instance variable can cause recursive frames to operate on stale pointers.

Not checking `l > r` base case

Missing base case leads to infinite recursion and stack overflow.

Crucial Edge Cases to Validate:

  • Empty Linked List (`head == null`) — Should immediately return null.
  • Single Element List (`[-10]`) — Correctly returns a single root node with left = null and right = null.
  • Two Element List (`[1, 2]`) — Root 1 with right child 2 (or root 2 with left child 1); height difference is 1, satisfying the AVL balance condition.
  • Large input (20,000 nodes) — The O(N) inorder method finishes in <10ms and avoids deep recursion stack overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both solutions: first propose the array conversion O(N) time & O(N) space, then offer the optimal O(N) time & O(log N) space Inorder Simulation.
  2. State the key insight clearly: 'Since BST inorder traversal is sorted order, we can simulate an inorder traversal and consume list nodes sequentially.'
  3. Highlight the logarithmic recursion stack memory guarantee.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does inorder simulation allow constructing the BST from a linked list in O(N) time without random indexing?

2.What is the primary drawback of using slow and fast pointers to find the midpoint at every recursive level?

3.In the optimal inorder simulation, when must the linked list head pointer be advanced to the next node?

Back to DSA Sheet