Convert Sorted List to Binary Search Tree
Medium · Linked List · Explanation and code example
Middle Node Divide and Conquer
How it works
The middle value of a sorted list is a suitable root for a balanced search tree. Slow and fast pointers locate it; detach the left half and recursively build the two subtrees. Repeating this split keeps subtree sizes close.
Steps
- Handle empty and one-node lists.
- Find the middle and disconnect its predecessor.
- Create the root and recursively build its left and right halves.
Complexity
- Time: O(n log n), because each recursion level scans its lists.
- Space: O(log n) recursion stack, excluding O(n) output tree.
Things to watch for
- This implementation disconnects links in the input list.
- Handle one node before accessing the middle predecessor.
- The resulting tree need not have one unique shape.
Python code example
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
def findMid(head: ListNode) -> ListNode:
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
return slow
if not head:
return None
if not head.next:
return TreeNode(head.val)
mid = findMid(head)
root = TreeNode(mid.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(mid.next)
return root
C++ code example
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr)
return nullptr;
if (!head->next)
return new TreeNode(head->val);
ListNode* mid = findMid(head);
TreeNode* root = new TreeNode(mid->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(mid->next);
return root;
}
private:
ListNode* findMid(ListNode* head) {
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
return slow;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.