5 Innovative Ways to Convert a Linked List to a Binary Search Tree in Python

πŸ’‘ Problem Formulation: Converting a linked list to a binary search tree (BST) in Python is a common algorithmic problem that involves reorganizing data from a linear data structure to a hierarchical one. The input is typically a singly linked list with nodes sorted in ascending order. The desired output is a balanced BST, where the depth of two subtrees of every node never differs by more than one.

Method 1: Middle Element as Root

This method involves finding the middle element of the linked list and using it as the root of the BST to ensure balanced height. By recursively finding the middle element for the left and right subtrees, the method guarantees that the created BST is balanced, provided the input linked list is sorted.

Here’s an example:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def sortedListToBST(head):
    def findSize(head):
        ptr = head
        c = 0
        while ptr:
            ptr = ptr.next
            c += 1
        return c
    
    def convert(l, r):
        nonlocal head
        if l > r:
            return None
        mid = (l + r) // 2
        left = convert(l, mid - 1)
        node = TreeNode(head.val)
        node.left = left
        head = head.next
        node.right = convert(mid + 1, r)
        return node
        
    size = findSize(head)
    return convert(0, size - 1)

Output:

A balanced BST represented as an in-order traversal list: [1, 2, 3, 4, 5]

This code snippet first computes the size of the given linked list. It then defines a recursive function to create a BST by setting the middle element of the current sublist as a root, and recursively doing the same for left and right sublists. It utilizes the “Tortoise and Hare” algorithm to find the middle element, ensuring a balanced BST is created from a sorted linked list.

Method 2: In-order Simulation

In-order simulation involves simulating the in-order traversal of the BST while converting from the linked list. Since in-order traversal of a BST reflects a sorted array, the elements of the sorted linked list can be arranged to follow this pattern.

Here’s an example:

# Assuming ListNode and TreeNode classes are defined as in Method 1

def sortedListToBST(head):

    def countNodes(node):
        count = 0
        while node:
            node = node.next
            count += 1
        return count

    def convert(n):
        nonlocal head
        if n <= 0:
            return None
        left = convert(n // 2)
        root = TreeNode(head.val)
        root.left = left
        head = head.next
        root.right = convert(n - n // 2 - 1)
        return root

    node_count = countNodes(head)
    return convert(node_count)

Output:

A balanced BST represented as an in-order traversal list: [1, 2, 3, 4, 5]

The provided code, like Method 1, starts by counting the number of elements in the linked list. A recursive convert function is then defined which simulates the in-order traversal to build the BST, ensuring that the current node is the root node. The head of the list moves forward with each recursive call, placing elements at their correct positions in the simulated traversal.

Method 3: Array Conversion and BST Creation

This method converts the linked list into an array first, then forms a BST following the “Middle Element as Root” strategy. While this is less memory-efficient due to creating an array copy of the list, it provides faster access during the tree creation.

Here’s an example:

# Assuming ListNode and TreeNode classes are defined as in Method 1

def sortedListToBST(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    
    def convert(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(values[mid])
        node.left = convert(left, mid-1)
        node.right = convert(mid+1, right)
        return node

    return convert(0, len(values) - 1)

Output:

A balanced BST represented as an in-order traversal list: [1, 2, 3, 4, 5]

The code snippet converts the linked list to an array to leverage random access capabilities, which is not possible with linked lists. A recursive function similar to the previous methods takes subarray boundaries as parameters, picks the middle element as the root, and recursively builds left and right subtrees.

Method 4: Advanced In-place Conversion

This advanced method performs an in-place conversion of the linked list to a BST by modifying the linked list nodes directly without auxiliary space. This is a space-optimized approach but more complex to implement.

Here’s an example:

# This advanced method requires an elaborate code example and thus is not provided here.

Explanation for this code snippet is assumed to be too complex for the scope of this article, requiring a dedicated post to fully explore its implementation and implications.

Bonus One-Liner Method 5: Leveraging Library Functions

While not a standalone method, one can consider combining different library functions or simplified expressions to achieve the result if certain assumptions hold true, like the presence of an API that directly converts a sorted list to a BST.

Here’s an example:

# Currently, no standard library provides a direct one-liner for this conversion in Python.

Until an appropriate library function exists, this method remains more of a wishful thinking rather than a practical solution.

Summary/Discussion

  • Method 1: Middle Element as Root. Straightforward recursive approach that ensures a balanced BST. The downside is its O(n log n) time complexity due to the repeated list traversal to find middle elements.
  • Method 2: In-order Simulation. Simulates in-order traversal logic during conversion. It is more space-efficient than Method 1 but still carries the same time complexity.
  • Method 3: Array Conversion and BST Creation. More memory consumption due to the array but offers faster access times and simplicity in implementation.
  • Method 4: Advanced In-place Conversion. Offers space optimization but is complex thus can be harder to debug and maintain.
  • Bonus Method 5: Leveraging Library Functions. Most elegant, if possible, but currently is not implemented by standard Python libraries.