Convert Sorted List to Binary Search Tree LeetCode Solution

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

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

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

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;
    }
};
Code language: C++ (cpp)

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;
    }
}
Code language: Java (java)

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)
};
Code language: JavaScript (javascript)

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
Code language: Python (python)