Table of Contents
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 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:
- 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 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