Last updated on July 16th, 2024 at 04:20 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

Topics

Depth First Search, Linked List

Companies

Zenefits

Level of Question

Medium

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-&gt;next) return new TreeNode(head-&gt;val);
            auto slow = head;
            auto fast = head;
            auto pre = head;
            while(fast &amp;&amp; fast-&gt;next) {
                pre = slow;
                slow = slow-&gt;next;
                fast = fast-&gt;next-&gt;next;
            }
            pre-&gt;next = 0; // break two halves 
            
            TreeNode* root = new TreeNode(slow-&gt;val);
            root-&gt;left = sortedListToBST(head);
            root-&gt;right = sortedListToBST(slow-&gt;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&amp;&amp;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) =&gt; {
        if (j &lt; i) return null
        let mid = i + j &gt;&gt; 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.