Convert Sorted List to Binary Search Tree LeetCode Solution

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

Convert Sorted List to Binary Search Tree LeetCode Solution

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.

Convert Sorted List to Binary Search Tree LeetCode Solution
fig-1
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 ComplexitySpace Complexity
C++O(n log n)O(log n)
JavaO(n log n)O(log n)
JavaScriptO(n log n)O(log n)
PythonO(n log n)O(log n)
Scroll to Top