Leetcode 109: Convert Sorted List to Binary Search Tree

Input: The input is a singly linked list with sorted elements.

Example: head = [-5, -2, 0, 3, 7, 10, 15]

Constraints:

• The number of nodes in the linked list is in the range [0, 20000].

• -10^5 <= Node.val <= 10^5

Output: The output is a height-balanced binary search tree represented by its root node.

Example: [0, -2, 10, -5, 3, 7, null]

Constraints:

• The binary search tree must be balanced in height, meaning that the depth of the subtrees at each node should not differ by more than 1.

Goal: The goal is to create a balanced binary search tree from a sorted singly linked list.

Steps:

• To create the height-balanced BST, recursively pick the middle element of the list as the root, and recursively do the same for the left and right sublists.

Goal: The solution should handle large inputs efficiently.

Steps:

• The list may contain up to 20,000 elements, so the solution needs to be optimized for time and space.

Assumptions:

• The input list is sorted in ascending order and contains no duplicates.

• Input: Input: head = [-10, -3, 0, 5, 9]

• Explanation: The linked list has 5 elements. The middle element, 0, will be the root. The left part of the list, [-10, -3], will form the left subtree, and the right part of the list, [5, 9], will form the right subtree.

• Input: Input: head = []

• Explanation: If the linked list is empty, the resulting binary search tree will also be empty.

Approach: The approach involves recursively selecting the middle element from the sorted linked list to ensure the resulting tree is height-balanced. This is done by finding the middle node of the list and making it the root, then applying the same process to the left and right halves.

Observations:

• Since the list is already sorted, we can easily identify the middle element to ensure the tree is balanced.

• The recursion ensures that each level of the tree remains balanced by selecting the middle of the list, dividing it into two smaller balanced subtrees.

Steps:

• Write a helper function to recursively convert the linked list into a balanced binary search tree.

• For each recursive call, identify the middle node of the list and create a new tree node for it.

• Use two pointers to find the middle element: one moves two steps at a time, and the other moves one step.

• Recursively call the function to build the left and right subtrees from the list segments on either side of the middle node.

Empty Inputs:

• If the input linked list is empty, return null as the result.

Large Inputs:

• The algorithm should efficiently handle large lists with up to 20,000 elements.

Special Values:

• Ensure that the solution handles negative values and large numbers within the specified range.

Constraints:

• Ensure that the function works correctly with both small and large inputs, efficiently processing lists with up to 20,000 elements.

TreeNode* toBST(ListNode* start, ListNode* end) {

    if(start == end) return NULL;

    ListNode* slw = start;
    ListNode* fst = start;

    while(fst != end && fst->next != end) {
        slw = slw->next;
        fst = fst->next->next;
    }

    TreeNode* node = new TreeNode(slw->val);
    node->left = toBST(start, slw);
    node->right = toBST(slw->next, end);
    return node;
}

TreeNode* sortedListToBST(ListNode* head) {
    if(head == NULL) return NULL;
    return toBST(head, NULL);
}

1 : Conditional Function Call

TreeNode* toBST(ListNode* start, ListNode* end) {

Define a recursive helper function to convert list segments into a BST.

2 : Base Case

if(start == end) return NULL;

Base case: If the start equals the end, return NULL as there are no nodes to process.

3 : Pointer Initialization

ListNode* slw = start;

Initialize a slow pointer to find the middle element of the linked list.

4 : Pointer Initialization

ListNode* fst = start;

Initialize a fast pointer to traverse the list twice as fast as the slow pointer.

5 : Loop Iteration

while(fst != end && fst->next != end) {

Move the slow and fast pointers until the fast pointer reaches the end of the segment.

6 : Pointer Movement

slw = slw->next;

Move the slow pointer one step forward.

7 : Pointer Movement

fst = fst->next->next;

Move the fast pointer two steps forward.

8 : Tree Initialization

TreeNode* node = new TreeNode(slw->val);

Create a new tree node with the value of the middle element (slow pointer).

9 : Recursive Call

node->left = toBST(start, slw);

Recursively construct the left subtree from the list segment before the middle element.

10 : Recursive Call

node->right = toBST(slw->next, end);

Recursively construct the right subtree from the list segment after the middle element.

11 : Return Value

return node;

Return the constructed tree node as the root of the current subtree.

12 : Function Declaration

TreeNode* sortedListToBST(ListNode* head) {

Define the main function to convert the sorted list to a BST.

13 : Base Case

if(head == NULL) return NULL;

Handle the edge case where the input list is empty.

14 : Recursive Call

return toBST(head, NULL);

Call the helper function to build the BST, starting with the entire list.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) since we traverse the entire linked list once to construct the tree.

Best Case: O(log n)

Worst Case: O(log n)

Description: The space complexity is O(log n) due to the recursive stack for the tree construction.

Leetcode 109: Convert Sorted List to Binary Search Tree

Solution to LeetCode 109: Convert Sorted List to Binary Search Tree Problem

Explore →