109. Convert Sorted List to Binary Search Tree

Description

The problem involves converting a sorted singly linked list into a height-balanced binary search tree (BST). A height-balanced BST is a binary tree in which the depth of the two subtrees of every node never differs by more than one. The challenge is to construct this BST while maintaining the order of elements in the linked list and ensuring the tree remains balanced.

Intuition

A binary search tree constructed from a sorted list should ideally have the middle element as the root, with the left half of the list forming the left subtree and the right half forming the right subtree. This guarantees that the tree is as balanced as possible, given the constraint of converting a list to a tree.

Approach

1. Convert List to Array: - Start by converting the linked list into an array. This allows us to easily access the middle element, which will be used to build the BST.
2. Recursive Tree Construction: - Implement a recursive function to build the tree. The function should take the current subarray (or segment of the list) as input. - The middle element of the subarray is selected as the root of the current subtree. - Recursively apply the same process to the left and right halves of the subarray to construct the left and right subtrees, respectively.
3. Base Case: - If the subarray is empty (i.e., start index exceeds the end index), return null, indicating that there are no more nodes to be added.

This approach ensures that the tree remains balanced and that the BST properties are maintained.

Complexity

Time Complexity:

The time complexity is (O(n)), where n is the number of nodes in the linked list. This is because each element is accessed once during the conversion to an array, and each node is visited once during the tree construction.

Space Complexity:

The space complexity is also (O(n)). This includes the space required for the array to store the node values and the space used by the recursion stack, which is proportional to the height of the tree (which is (O(\log n)) in the case of a balanced tree).

Code

C++

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        // Convert the linked list to an array
        std::vector values;
        while (head) {
            values.push_back(head->val);
            head = head->next;
        }
        
        // Recursively construct the BST
        return buildTree(values, 0, values.size() - 1);
    }

private:
    TreeNode* buildTree(const std::vector& values, int start, int end) {
        if (start > end) return nullptr;

        int mid = start + (end - start) / 2;
        TreeNode* node = new TreeNode(values[mid]);

        node->left = buildTree(values, start, mid - 1);
        node->right = buildTree(values, mid + 1, end);

        return node;
    }
};

Python

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        # Convert the linked list to an array
        values = []
        while head:
            values.append(head.val)
            head = head.next

        # Recursively construct the BST
        def build_tree(values):
            if not values:
                return None

            mid = len(values) // 2
            node = TreeNode(values[mid])

            node.left = build_tree(values[:mid])
            node.right = build_tree(values[mid + 1:])

            return node

        return build_tree(values)

Java

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        // Convert the linked list to an array
        List values = new ArrayList<>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }

        // Recursively construct the BST
        return buildTree(values, 0, values.size() - 1);
    }

    private TreeNode buildTree(List values, int start, int end) {
        if (start > end) return null;

        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(values.get(mid));

        node.left = buildTree(values, start, mid - 1);
        node.right = buildTree(values, mid + 1, end);

        return node;
    }
}

JavaScript

var sortedListToBST = (h, a = []) => {
    while (h) a.push(h.val), h = h.next

    let result = a => {
        if (!a.length) return null

        let i = Math.floor(a.length / 2), v = a[i]
        let node = new TreeNode(v)

        node.left = result(a.slice(0, i))
        node.right = result(a.slice(i + 1))

        return node
    }

    return result(a)
}