algoadvance

Leetcode 109. Convert Sorted List to Binary Search Tree

Problem Statement

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Clarifying Questions

1. Input Format:
   • A singly linked list where each node contains an integer value.
2. Output Format:
   • The root of the height-balanced BST.
3. Length of Input List:
   • Are there any constraints on the length of the linked list (e.g., maximum length)?
4. Type of Balanced Tree:
   • Are there specific rules for the balance, or is it the standard definition where the heights of the two child subtrees of any node differ by at most one?
5. Edge Cases:
   • What should be returned if the linked list is empty? (Answer: Return nullptr)

Assumptions:

• The linked list can contain both positive and negative integers.
• The linked list has no duplicate elements.

Strategy

To convert a sorted linked list to a height-balanced BST:

1. Find the Middle Element: The middle element of the linked list will serve as the root of the BST for that segment. This will help maintain the balance of the BST.
2. Recursive Approach: Recursively apply the same logic to the sublists before and after the middle element:
   • The sublist before the middle element will form the left subtree.
   • The sublist after the middle element will form the right subtree.

Code

Here is the code to achieve this:

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);

        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;

        // Find the middle of the linked list
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        // Disconnect the left half list
        if (prev) {
            prev->next = nullptr;
        }

        // The middle element is the root of the BST
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);      // Recursively build the left subtree
        root->right = sortedListToBST(slow->next);   // Recursively build the right subtree

        return root;
    }
};

Time Complexity

• Finding the Middle Node: It takes O(n) for the entire linked list.
• Recursive Construction: Each recursive call halves the number of nodes it processes.
• The overall time complexity is O(n log n) where n is the number of nodes in the linked list.

Space Complexity

• Recursive Stack: The space complexity is O(log n) due to the recursion stack space needed for the depth of the constructed tree.

This solution ensures that the tree is balanced since we are always splitting the list around its middle.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?