LeetCode 109: Convert Sorted List to Binary Search Tree Solution

Master LeetCode problem 109 (Convert Sorted List to Binary Search Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

109. Convert Sorted List to Binary Search Tree

Medium

Linked List Divide and Conquer Tree Binary Search Tree Binary Tree

Problem Explanation

Explanation

To convert a sorted linked list to a balanced binary search tree, we can follow a divide-and-conquer approach. The idea is to find the middle element of the linked list as the root of the current subtree. Recursively construct the left subtree from the left half of the list and the right subtree from the right half of the list.

Find the middle element by using two pointers technique (slow and fast pointers).
Recursively build the left subtree with the elements before the middle element.
Make the middle element as the root of the current subtree.
Recursively build the right subtree with the elements after the middle element.

The time complexity of this approach is O(n log n) where n is the number of elements in the linked list, and the space complexity is O(log n) due to the recursive calls on the stack.

Solution Code

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        
        ListNode mid = findMiddle(head);
        
        TreeNode root = new TreeNode(mid.val);
        
        if (head == mid) return root;
        
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        
        return root;
    }
    
    private ListNode findMiddle(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;
        
        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        
        if (prevPtr != null) {
            prevPtr.next = null;
        }
        
        return slowPtr;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 109 (Convert Sorted List to Binary Search Tree)?

This page provides optimized solutions for LeetCode problem 109 (Convert Sorted List to Binary Search Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 109 (Convert Sorted List to Binary Search Tree)?

The time complexity for LeetCode 109 (Convert Sorted List to Binary Search Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 109 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 109 in Java, C++, or Python.

Back to LeetCode Solutions