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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert Sorted List to Binary Search Tree

Difficulty: Medium

Problem Description

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

Key Insights

  • The linked list is sorted, which allows us to use the middle element as the root of the BST to maintain balance.
  • The tree is height-balanced if the depth of the two subtrees of any node never differs by more than one.
  • We can use a recursive approach to divide the linked list into two halves, building the tree as we go.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, as we visit each node exactly once. Space Complexity: O(log n) for the recursion stack in the case of a balanced tree (worst-case O(n) for an unbalanced tree).

Solution

To convert a sorted linked list to a height-balanced binary search tree, we can use a recursive approach. The steps are as follows:

  1. Find the middle element of the linked list. This will be the root of the BST.
  2. Recursively do the same for the left half and the right half of the list.
  3. The left subtree will be built from the left half, and the right subtree will be built from the right half.

This way, we ensure that the tree is balanced by always choosing the middle element as the root.

Code Solutions

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):
    if not head:
        return None
    
    # Function to find the middle element
    def findMiddle(left, right):
        slow = left
        fast = left
        while fast != right and fast.next != right:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    # Recursive function to build the tree
    def convert(left, right):
        if left == right:
            return None
        
        mid = findMiddle(left, right)
        node = TreeNode(mid.val)
        node.left = convert(left, mid)
        node.right = convert(mid.next, right)
        return node
    
    return convert(head, None)
← Back to All Questions