NUHMAN.com

Introduction

LeetCode 109: Convert Sorted List to Binary Search Tree asks you to convert a sorted linked list into a Binary Search Tree (BST). The resulting BST must be height-balanced. This problem requires an efficient solution to transform a sorted linked list into a balanced binary search tree.

Since the list is already sorted, the key observation is to use the middle element of the linked list as the root of the BST. This ensures the tree remains balanced, and it can be done using the slow and fast pointer technique to find the middle element of the list.

Problem Statement

Given the head of a singly linked list head where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

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 1.

Example:

go

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

Approach:

Using Fast and Slow Pointers

To solve this problem, we need to find the middle element of the linked list, which will be the root of the binary search tree. This can be done using the fast and slow pointer technique:

1. Base Case: If the linked list is empty or contains only one element, return nil or the single node as the root of the tree.
2. Finding the Middle:

• Use two pointers, slow and fast. The fast pointer moves twice as fast as the slow pointer. By the time fast reaches the end of the list, slow will be at the middle element.

1. Recursive Construction:

• The element found by the slow pointer will be the root of the current subtree.
• Recursively build the left and right subtrees using the elements before and after the middle element.
• This process ensures that the tree remains balanced.

Go Implementation

Solution Using Fast and Slow Pointer

go

package main

// ListNode represents a node in the singly linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// sortedListToBST converts a sorted linked list to a height-balanced binary search tree.
func sortedListToBST(head *ListNode) *TreeNode {
    // Find the size of the linked list.
    size := 0
    current := head
    for current != nil {
        size++
        current = current.Next
    }

    // Use helper function to build the BST.
    return buildTree(&head, 0, size-1)
}

// buildTree is a helper function that constructs the BST recursively.
func buildTree(head **ListNode, left, right int) *TreeNode {
    if left > right {
        return nil
    }

    mid := (left + right) / 2

    // Recursively build the left subtree.
    leftChild := buildTree(head, left, mid-1)

    // The middle element is the root of the current subtree.
    root := &TreeNode{Val: (*head).Val}
    root.Left = leftChild

    // Move to the next element in the list.
    *head = (*head).Next

    // Recursively build the right subtree.
    root.Right = buildTree(head, mid+1, right)

    return root
}

Explanation:

1. ListNode and TreeNode Structures:

• The ListNode struct represents a node in the singly linked list. Each node has a value (Val) and a pointer to the next node (Next).
• The TreeNode struct represents a node in the binary tree. Each node has a value (Val), and pointers to the left and right children (Left and Right).

1. sortedListToBST Function:

• This is the main function that takes the head of the sorted linked list and returns the root of the constructed height-balanced binary search tree.
• First, it calculates the size of the linked list by iterating through it.
• Then it calls the helper function buildTree, passing the head of the list and the size of the list to construct the tree recursively.

1. buildTree Function:

• This is the helper function that builds the BST recursively:
• Base Case: If left is greater than right, return nil.
• Recursive Case:
• Calculate the middle index (mid).
• Recursively construct the left subtree by calling buildTree on the left half of the list.
• The middle element of the list becomes the root of the current subtree.
• Move the head pointer to the next element in the list.
• Recursively construct the right subtree by calling buildTree on the right half of the list.

1. Why Fast and Slow Pointers:

• The slow pointer will reach the middle element of the list, which we use as the root of the tree. This ensures that the tree is balanced, as the elements are split evenly between the left and right subtrees.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

• n is the number of nodes in the linked list (or the number of nodes in the binary search tree).

Time Complexity:

• The time complexity is O(n) because we traverse the linked list once to compute its size, and the buildTree function processes each node in the list exactly once.

Space Complexity:

• The space complexity is O(n) due to the recursion stack used to build the binary search tree. Each recursive call adds one level to the stack, and since the depth of the recursion is proportional to the height of the tree, the space complexity is O(n) in the worst case.

Edge Cases

1. Empty List:

• Input: head = nil
• Output: nil
• Explanation: An empty linked list results in an empty tree.

1. Single Element List:

• Input: head = [1]
• Output: [1]
• Explanation: A single element in the list results in a tree with one node.

1. Multiple Elements:

• Input: head = [-10,-3,0,5,9]
• Output: [0,-3,9,-10,null,5]
• Explanation: The middle element (0) becomes the root, and the left and right subtrees are recursively built.

Conclusion

LeetCode 109: Convert Sorted List to Binary Search Tree is a problem that requires converting a sorted linked list into a height-balanced binary search tree. Using the fast and slow pointer technique to find the middle element, we can efficiently build the binary search tree with a time complexity of O(n). This approach ensures that the tree remains balanced, and the problem serves as a great exercise in recursive tree construction and linked list manipulation.