Last updated on January 29th, 2025 at 02:30 am
Here, we see a Convert Sorted List to Binary Search Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Depth First Search, Linked List
Companies
Zenefits
Level of Question
Medium

Convert Sorted List to Binary Search Tree LeetCode Solution
Table of Contents
1. 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.

Example 1: (fig-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: []
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Fast & Slow Pointers. This pattern is commonly used to find the middle of a linked list, detect cycles, or solve problems involving linked lists efficiently. In this case, the Fast & Slow Pointers technique is used to find the middle node of the linked list, which is then used as the root of the Binary Search Tree (BST).
3. Code Implementation in Different Languages
3.1 Convert Sorted List to Binary Search Tree C++
class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if(!head) return NULL; if(!head->next) return new TreeNode(head->val); auto slow = head; auto fast = head; auto pre = head; while(fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = 0; // break two halves TreeNode* root = new TreeNode(slow->val); root->left = sortedListToBST(head); root->right = sortedListToBST(slow->next); return root; } };
3.2 Convert Sorted List to Binary Search Tree Java
class Solution { public TreeNode sortedListToBST(ListNode head) { if(head==null) return null; return toBST(head,null); } public TreeNode toBST(ListNode head, ListNode tail){ ListNode slow = head; ListNode fast = head; if(head==tail) return null; while(fast!=tail&&fast.next!=tail){ fast = fast.next.next; slow = slow.next; } TreeNode thead = new TreeNode(slow.val); thead.left = toBST(head,slow); thead.right = toBST(slow.next,tail); return thead; } }
3.3 Convert Sorted List to Binary Search Tree JavaScript
var sortedListToBST = function(head) { let curr = head, count = 0 while (curr) curr = curr.next, count++ const treeify = (i, j) => { if (j < i) return null let mid = i + j >> 1, node = new TreeNode() node.left = treeify(i, mid - 1) node.val = curr.val, curr = curr.next node.right = treeify(mid + 1, j) return node } curr = head return treeify(1, count) };
3.4 Convert Sorted List to Binary Search Tree Python
class Solution(object): def sortedListToBST(self, head): if not head: return if not head.next: return TreeNode(head.val) slow, fast = head, head.next.next while fast and fast.next: fast = fast.next.next slow = slow.next tmp = slow.next slow.next = None root = TreeNode(tmp.val) root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(tmp.next) return root
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n log n) | O(log n) |
Java | O(n log n) | O(log n) |
JavaScript | O(n log n) | O(log n) |
Python | O(n log n) | O(log n) |