# Implement Sorted Linked List to Balanced Binary Search Tree

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:

• Find the middle of the left subtree and make it the root. We return it so it can be assigned as the left child of the root.
• Similarly, get the middle of the right subtree and make it the root. We return it so it can be assigned as the right child. ### 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
slow = None
while fast and fast.next:
if slow == None:
else:
slow = slow.next
fast = fast.next.next
return slow

return None

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.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
def __init__(self):

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
else:
#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.insert(-5)
ll.insert(-3)
ll.insert(0)
ll.insert(3)
ll.insert(5)

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:

• Get the index of the middle element in the Linked List. Construct the left subtree from the first half of nodes.
• After that, we get the root of the BST, which is the middle node.
• At last, we create the right subtree from the right half of nodes.

###  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
count = 0
while temp:
count += 1
temp = temp.next
return count

def bottomUpConvert(start, end):
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

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

def convertSortedListToBST(h):
length = getLength(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
def __init__(self):

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
else:
#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.insert(-5)
ll.insert(-3)
ll.insert(0)
ll.insert(3)
ll.insert(5)

print("Pre-Order Traversal of the converted BST")
preOrder(bst)
```

Output

```0
-5
-3
3
5
```

Back to: Data Structure > Data Structure - Linked List