Convert Sorted List to Binary Search Tree solution and explanation
Google
TCS
9 more videos on this problem
Convert Sorted List to Binary Search Tree | Google | Flipkart | Amazon | Leetcode 109codestorywithMIK · 22:29 · 18K views
Convert Sorted List to BST | LeetCode 109 | Google Coding Interview QuestionEazyAlgo · 9:50 · 11K views
Convert Sorted List to Binary Search Tree (BST) | LeetCode 109 | C++, Java, PythonKnowledge Center · 18:43 · 10K views
Leetcode - Convert Sorted List to Binary Search Tree (Python)Timothy H Chang · 5:25 · 6K views
LeetCode 109. Convert Sorted List to Binary Search TreeHappy Coding · 13:53 · 3K views
Convert sorted list to binary search tree | Leetcode 109Coding Decoded · 10:24 · 734 views
Daily Leetcode #1075: Mar 11, 2023 - 109. Convert Sorted List to Binary Search TreeProgramming Live with Larry · 17:49 · 545 views
109. Convert Sorted List to Binary Search Tree - JAVA (Divide & Conquer - Recursion)Sourin Majumdar · 13:37 · 462 views
Convert Sorted List to Binary Search Tree | LeetCode 109 | Coders CampCoders Camp · 10:25 · 249 views
Convert Sorted List to Binary Search Tree - Leetcode 109 - PythonLit Code · 6:50 · 246 views
The problem
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Example 1:
Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Example 2:
Input: head = [] Output: []
Constraints:
- The number of nodes in
headis in the range[0, 2 * 104]. -105 <= Node.val <= 105
Approach overview
Problem Overview: You receive the head of a sorted singly linked list and must convert it into a height-balanced binary search tree. The BST property must hold (left < root < right) while keeping the tree balanced so operations remain efficient.
Approach 1: Convert Linked List to Array (O(n) time, O(n) space)
The simplest strategy is to copy the linked list values into an array. Once stored in an array, the problem becomes identical to building a balanced BST from a sorted array. Recursively choose the middle index as the root, build the left subtree from the left half, and the right subtree from the right half. Array indexing gives constant-time access to the middle element, so the recursion runs in O(n) time with O(n) extra space for the array. This approach is easy to reason about and often preferred when clarity matters more than strict memory usage.
Approach 2: Fast and Slow Pointer (O(n log n) time, O(log n) space)
This approach avoids converting the list into an array. Use the classic fast and slow pointer technique to locate the middle node of the linked list, which becomes the root of the BST. Recursively apply the same logic to the left portion of the list (before the middle) and the right portion (after the middle). Finding the middle node takes linear time each recursion level, and the recursion depth is O(log n), producing a total time complexity of O(n log n). Only recursion stack space is used, so extra space is O(log n). This method demonstrates deeper understanding of linked list traversal and divide and conquer.
Recommended for interviews: Interviewers typically expect the fast–slow pointer solution because it shows you understand how to manipulate a linked list without converting it to another structure. Starting with the array approach is still valuable—it proves you recognize the relationship between a sorted sequence and a balanced binary search tree. Then improving it to the in-place divide-and-conquer version demonstrates stronger problem-solving skills.
Approach 1: Approach 1: Convert Linked List to Array
This approach involves converting the linked list to an array and then using the middle of the array to create a height-balanced binary search tree (BST). The middle of the array will become the root, and this concept is applied recursively to the left and right halves of the array.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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: ListNode) -> TreeNode:
values = []
while head:
values.append(head.val)
head = head.next
def convertListToBST(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(values[mid])
if left == right:
return node
node.left = convertListToBST(left, mid - 1)
node.right = convertListToBST(mid + 1, right)
return node
return convertListToBST(0, len(values) - 1)class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function sortedListToBST(head) {
const values = [];
while (head !== null) {
values.push(head.val);
head = head.next;
}
function convertListToBST(left, right) {
if (left > right) return null;
const mid = Math.floor((left + right) / 2);
const node = new TreeNode(values[mid]);
if (left === right) return node;
node.left = convertListToBST(left, mid - 1);
node.right = convertListToBST(mid + 1, right);
return node;
}
return convertListToBST(0, values.length - 1);
}The solution first converts the linked list into an array for easy access. It then uses the middle element of the array as the root of the BST and recursively applies this method to the left and right segments of the list. This way, a height-balanced BST is created.
Time Complexity: O(n), where n is the number of nodes in the linked list, because we traverse the list to create the array.
Space Complexity: O(n), for storing the values in the array.
Approach 2: Approach 2: Fast and Slow Pointer
This approach uses the slow and fast pointer technique to find the middle of the linked list, which forms the root of the BST. The linked list is recursively divided into two halves, and this method is used to create the left and right subtrees.
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return convertToBST(head, null);
}
private TreeNode convertToBST(ListNode head, ListNode tail) {
if (head == tail) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
TreeNode node = new TreeNode(slow.val);
node.left = convertToBST(head, slow);
node.right = convertToBST(slow.next, tail);
return node;
}
}struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return nullptr;
return convertToBST(head, nullptr);
}
TreeNode* convertToBST(ListNode* head, ListNode* tail) {
if (head == tail) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != tail && fast->next != tail) {
slow = slow->next;
fast = fast->next->next;
}
TreeNode* node = new TreeNode(slow->val);
node->left = convertToBST(head, slow);
node->right = convertToBST(slow->next, tail);
return node;
}
};The Java solution uses a recursive function, with fast and slow pointers to find the middle of the linked list. This middle element becomes the root of the BST, and the process is applied to the list segments left and right of the middle to form the subtrees.
Time Complexity: O(n log n), because cutting the list in half at each step takes O(log n) splits, and each split involves a linear scan.
Space Complexity: O(log n), for the recursion stack where n is the number of nodes in the list.
Approach 3: DFS
We first convert the linked list to an array nums, and then use depth-first search to construct the binary search tree.
We define a function dfs(i, j), where i and j represent the current interval [i, j]. Each time, we choose the number at the middle position mid of the interval as the root node, recursively construct the left subtree for the interval [i, mid - 1], and the right subtree for the interval [mid + 1, j]. Finally, we return the node corresponding to mid as the root node of the current subtree.
In the main function, we just need to call dfs(0, n - 1) and return the result.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sortedListToBST(head: ListNode | null): TreeNode | null {
const nums: number[] = [];
for (; head; head = head.next) {
nums.push(head.val);
}
const dfs = (i: number, j: number): TreeNode | null => {
if (i > j) {
return null;
}
const mid = (i + j) >> 1;
const left = dfs(i, mid - 1);
const right = dfs(mid + 1, j);
return new TreeNode(nums[mid], left, right);
};
return dfs(0, nums.length - 1);
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* dfs(int* nums, int i, int j) {
if (i > j) {
return NULL;
}
int mid = (i + j) >> 1;
struct TreeNode* left = dfs(nums, i, mid - 1);
struct TreeNode* right = dfs(nums, mid + 1, j);
struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->val = nums[mid];
root->left = left;
root->right = right;
return root;
}
struct TreeNode* sortedListToBST(struct ListNode* head) {
int size = 0;
struct ListNode* temp = head;
while (temp) {
size++;
temp = temp->next;
}
int* nums = (int*) malloc(size * sizeof(int));
temp = head;
for (int i = 0; i < size; i++) {
nums[i] = temp->val;
temp = temp->next;
}
struct TreeNode* root = dfs(nums, 0, size - 1);
free(nums);
return root;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
nums := []int{}
for ; head != nil; head = head.Next {
nums = append(nums, head.Val)
}
var dfs func(i, j int) *TreeNode
dfs = func(i, j int) *TreeNode {
if i > j {
return nil
}
mid := (i + j) >> 1
left := dfs(i, mid-1)
right := dfs(mid+1, j)
return &TreeNode{nums[mid], left, right}
}
return dfs(0, len(nums)-1)
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn sorted_list_to_bst(head: Option<Box<ListNode>>) -> Option<Rc<RefCell<TreeNode>>> {
let mut nums = Vec::new();
let mut current = head;
while let Some(node) = current {
nums.push(node.val);
current = node.next;
}
fn dfs(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
if nums.is_empty() {
return None;
}
let mid = nums.len() / 2;
Some(Rc::new(RefCell::new(TreeNode {
val: nums[mid],
left: dfs(&nums[..mid]),
right: dfs(&nums[mid + 1..]),
})))
}
dfs(&nums)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Convert Linked List to Array | Time Complexity: O(n), where n is the number of nodes in the linked list, because we traverse the list to create the array. |
| Approach 2: Fast and Slow Pointer | Time Complexity: O(n log n), because cutting the list in half at each step takes O(log n) splits, and each split involves a linear scan. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert Linked List to Array | O(n) | O(n) | When simplicity matters and extra memory is acceptable |
| Fast and Slow Pointer (Divide and Conquer) | O(n log n) | O(log n) | When you want an in-place linked list solution with minimal extra memory |
Frequently asked questions
Is Convert Sorted List to Binary Search Tree easy or hard?
Convert Sorted List to Binary Search Tree is rated Medium on LeetCode. The main challenge is recognizing that the middle element must become the root to maintain balance while handling linked list traversal efficiently.
How to solve Convert Sorted List to Binary Search Tree in O(n)?
Achieving O(n) time typically involves first copying the linked list values into an array. Once stored in an array, you can build a balanced BST by recursively choosing the middle element as the root. Each element is processed once, producing overall O(n) time.
Convert Sorted List to Binary Search Tree Python or Java solution?
Python and Java solutions usually follow two patterns: convert the linked list to an array and build the BST using the middle index, or use fast and slow pointers to find the middle node directly in the list. Both approaches recursively construct left and right subtrees.
What is the best approach for Convert Sorted List to Binary Search Tree?
The fast and slow pointer approach is usually considered the best interview solution. It finds the middle node of the linked list to use as the root and recursively builds left and right subtrees. This method avoids converting the list into another structure and uses only O(log n) recursion space.
What data structure is used in Convert Sorted List to Binary Search Tree?
The problem primarily uses a singly linked list as input and constructs a binary search tree as output. Solutions commonly rely on recursion, the fast–slow pointer technique, and divide-and-conquer to maintain BST ordering and balance.
What is the time complexity of Convert Sorted List to Binary Search Tree?
Time complexity depends on the approach. Converting the linked list to an array and then building a BST takes O(n) time. The fast–slow pointer approach repeatedly scans for the middle node, leading to O(n log n) time with O(log n) recursion stack space.
Is Convert Sorted List to Binary Search Tree asked at Google, Amazon, or Meta?
Convert Sorted List to Binary Search Tree appears in many technical interview prep lists and has been reported in interviews at companies like Amazon, Google, and Meta. The problem tests linked list traversal, recursion, and understanding of balanced binary search trees.