In this article, we will implement a balanced Binary Search Tree(BST) from a sorted Linked List. A binary tree is considered balanced if the height of the left subtree and the height of the right subtree of every node differ by no more than 1.

Approach 1 (O(nlogn) Time Complexity)

This is a recursive approach, and it involves finding the middle of the linked list and dividing the list into two halves.

First, we find the middle of the linked list and assign it as the BST’s root. We get the middle node using the two-pointer (slow and fast) approach. Then, we divide the list into two halves, left and right.

We recursively do the following to find the left and right subtree:

Implementation of Sorted Linked List to Balanced BST Using O(nlogn) Time Complexity

The code is given below.

#node for the linked list
class Node:
  def __init__(self,value=None):
    self.value = value
    self.next = None
 
#node for the binary search tree
class NodeTree:
    def __init__(self, value, left=None, right=None):
      self.value = value
      self.left = left
      self.right = right
 
#this method finds the node just before the middle node
def getMiddle(head):
  slow = None
  fast = head
  while fast and fast.next:
    if slow == None:
      slow = head
    else:
      slow = slow.next
    fast = fast.next.next
  return slow
 
def convertSortedListToBST(head):
  if head == None:
    return None
  if head.next == None:
    return NodeTree(head.value)
  
  before_mid = getMiddle(head) #get the node before the middle node
  root = NodeTree(before_mid.next.value) #make the middle node the root
        
  right_half = before_mid.next.next # get the right half
  before_mid.next = None #set the end for the left half
 
  root.left = convertSortedListToBST(head) 
  root.right = convertSortedListToBST(right_half)
 
  return root
 
 
#pre order traversal for the balanced binary
def preOrder(root):
  if root != None:
    print(root.value)
    preOrder(root.left)
    preOrder(root.right)
 
 
#implementation of linked list for testing
class LinkedList:
  def __init__(self):
    self.head = None
  
  #add a value in the linked list 
  def insert(self, value):
    node = Node(value) #create a node
    if self.head == None: #if list is empty insert a value(node) at the start
      self.head = node
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
          temp = temp.next 
      temp.next = node #adding a new node


#create sorted linked list for test drive
ll = LinkedList()
ll.insert(-5)
ll.insert(-3)
ll.insert(0)
ll.insert(3)
ll.insert(5)

bst = convertSortedListToBST(ll.head)
print("Pre-Order Traversal of the converted BST")
preOrder(bst)

Output

Pre-Order Traversal of the converted BST
0
-3
-5
5
3

The time complexity of this algorithm is O(nlogn). Here, n is the length of the linked list. However, we can find a better solution.

Approach 2 (O(n) Time Complexity)

The above-given approach creates the BST in a top-down manner, i.e., we get the root first and then the leaves. On the contrary, this solution uses the bottom-up approach, i.e., we will go from the leaves to the root. Here, we start constructing the BST in the same order as values occur in the linked list. Moreover, we iterate over the linked list two times. In each pass, we visit an element exactly once. Therefore, the time complexity becomes O(n).

The algorithm is as follows:

First, we iterate over the linked list and find its length.

Then, we recursively do the following:

Implement Sorted Linked List to Balanced BST using O(n) Time Complexity

The implementation is given below.

#node for the linked list
class Node:
  def __init__(self,value=None):
    self.value = value
    self.next = None
 
#node for the binary search tree
class NodeTree:
    def __init__(self, value, left=None, right=None):
      self.value = value
      self.left = left
      self.right = right
 
 #this method finds the length of the linked list
def getLength(head):
  temp = head
  count = 0
  while temp:
    count += 1
    temp = temp.next
  return count

def bottomUpConvert(start, end):
  global head
  if start <= end:
    mid = (start + end)//2 #find the middle index

    left = bottomUpConvert(start, mid-1) #make the left subtree from first half recursively

    root = NodeTree(head.value) #create the root node from the middle value
   
    head = head.next #increment the list

    root.left = left #assign left subtree as the left child of the root
    right = bottomUpConvert(mid+1, end) #make the right subtree from right half recursively
    root.right = right #assign right subtree as the right child of the root
    return root
  else:
    return None

head = None
def convertSortedListToBST(h):
  global head
  length = getLength(h)
  head = h
  return bottomUpConvert(0, length-1)

#pre order traversal for the balanced binary
def preOrder(root):
  if root != None:
    print(root.value)
    preOrder(root.left)
    preOrder(root.right)
 
 
#implementation of linked list for testing
class LinkedList:
  def __init__(self):
    self.head = None
  
  #add a value in the linked list 
  def insert(self, value):
    node = Node(value) #create a node
    if self.head == None: #if list is empty insert a value(node) at the start
      self.head = node
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
          temp = temp.next 
      temp.next = node #adding a new node

#create sorted linked list for test drive
ll = LinkedList()
ll.insert(-5)
ll.insert(-3)
ll.insert(0)
ll.insert(3)
ll.insert(5)

bst = convertSortedListToBST(ll.head)
print("Pre-Order Traversal of the converted BST")
preOrder(bst)

Output

0
-5
-3
3
5