Convert Sorted List to Binary Search Tree LeetCode Solution

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

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.

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

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)
Scroll to Top