We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert Sorted List to Binary Search Tree

Number: 109

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Microsoft, Uber, Bloomberg, Apple, Lyft, Zenefits

Problem Description

Given the head of a singly linked list 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 one.

Key Insights

  • The list is sorted in ascending order, which allows us to apply a divide and conquer approach.
  • The middle element of the list should be the root of the BST to ensure the tree is balanced.
  • Recursively repeating the process for the left and right segments of the list constructs the left and right subtrees.
  • Two popular approaches are:
    • Convert the list to an array and then use two pointers for recursion.
    • Use slow and fast pointers to find the middle element without extra space.

Space and Time Complexity

Time Complexity: O(n) if using the in-order simulation approach; O(n log n) if repeatedly finding the middle with two pointers.
Space Complexity: O(log n) for the recursion stack (assuming the conversion to array uses O(n) extra space in that approach).

Solution

We solve the problem using a divide and conquer method by first converting the linked list into an array, which allows for easy access to the middle element. The middle element is chosen as the root of the BST, and the left half of the array is used to build the left subtree while the right half constructs the right subtree. This method guarantees that the height difference between the subtrees is minimized, resulting in a height-balanced BST.
Key data structures used:

  • Array (to store linked list values)
  • Tree nodes to build the BST
    The algorithm recursively computes the middle index and creates tree nodes until the entire array is processed.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # Convert linked list to array for easier middle element access
        values = []
        while head:
            values.append(head.val)
            head = head.next

        # Helper function to build BST from sorted array
        def buildBST(left, right):
            if left > right:
                return None
            mid = (left + right) // 2  # Choose middle element as root for balance
            node = TreeNode(values[mid])
            # Recursively build left subtree
            node.left = buildBST(left, mid - 1)
            # Recursively build right subtree
            node.right = buildBST(mid + 1, right)
            return node

        # Build BST using the helper function
        return buildBST(0, len(values) - 1)
← Back to All Questions