109. Convert Sorted List to Binary Search Tree LeetCode Solution
In this guide, you will get 109. Convert Sorted List to Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Convert Sorted List to Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Convert Sorted List to Binary Search Tree
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 head is in the range [0, 2 * 104].
-105 <= Node.val <= 105
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(\log n)
109. Convert Sorted List to Binary Search Tree LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
109. Convert Sorted List to Binary Search Tree LeetCode Solution in Java
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
if (head.next == null)
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 = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return slow;
}
} // code provided by PROGIEZ
109. Convert Sorted List to Binary Search Tree LeetCode Solution in Python
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 # code by PROGIEZ
