Last updated on October 10th, 2024 at 12:55 am

Here, We see Convert Sorted List to Binary Search Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Convert Sorted List to Binary Search Tree LeetCode Solution

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: []

1. Convert Sorted List to Binary Search Tree Leetcode Solution 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;
    }
};

1.1 Explanation

• Base Cases: If the list is empty, return NULL. If there is only one node, return a new TreeNode with that value.
• Find Middle: Use a slow and fast pointer to find the middle node of the list. The slow pointer will be the middle node when fast reaches the end.
• Break the List: Break the list into two halves by setting the next pointer of the node before slow to NULL.
• Recursive Calls: Recursively call sortedListToBST on the left and right halves to construct the left and right subtrees.
• Construct Root: Create a new TreeNode with the value of the middle node and assign the left and right subtrees.

1.2 Time Complexity

• O(n log n).

1.3 Space Complexity

• O(log n).

2. Convert Sorted List to Binary Search Tree Leetcode Solution 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;
    }
}

2.1 Explanation

• Base Case: If head is null, return null.
• Recursive Helper Function: Use a helper function toBST with parameters head and tail to handle the recursive calls.
• Find Middle: Use slow and fast pointers to find the middle node.
• Recursive Calls: Recursively call toBST on the left and right halves.
• Construct Root: Create a new TreeNode with the value of the middle node and assign the left and right subtrees.

2.2 Time Complexity

• O(n log n).

2.3 Space Complexity

• O(log n) due to the recursion stack.

3. Convert Sorted List to Binary Search Tree Leetcode Solution 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.1 Explanation

• Count Nodes: Count the number of nodes in the list.
• Treeify Function: A recursive function to construct the BST from the list.
• Base Case: If the end index is less than the start index, return null.
• Find Middle: Calculate the middle index and create a new TreeNode.
• Recursive Calls: Recursively call treeify on the left and right halves.

3.2 Time Complexity

• O(n).

3.3 Space Complexity

• O(log n) due to the recursion stack.

4. Convert Sorted List to Binary Search Tree Leetcode Solution 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.1 Explanation

• Base Cases: If the list is empty, return None. If there is only one node, return a new TreeNode with that value.
• Find Middle: Use a slow and fast pointer to find the middle node of the list.
• Break the List: Break the list into two halves by setting the next pointer of the node before slow to None.
• Recursive Calls: Recursively call sortedListToBST on the left and right halves to construct the left and right subtrees.
• Construct Root: Create a new TreeNode with the value of the middle node and assign the left and right subtrees.

4.2 Time Complexity

• O(n log n).

4.3 Space Complexity

• O(log n) due to the recursion stack.