# Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Objec­tive: You have been given a sorted singly List, you need to con­vert it into bal­anced binary search tree.

Why bal­anced binary tree is important:

You can also cre­ate first node as root and insert all other nodes to the right of the tree because List is in increas­ing order but this con­structed tree won’t be bal­anced tree, it wil be skwed tree and to per­form oper­a­tions on this tree will be O(n) not O(logn).

Input: An sorted Singly Linked List

Out­put: Bal­anced Binary Tree

Exam­ple:

Appraoch:

• Say mid is the mid­dle node in the linked list.
• Recur­sively con­struct left sub­tree from start to mid-1
• Make the mid­dle node as root and assign the left sub­tree to it.
• Recur­sively con­struct right sub­tree from mid+1 to end.
• Assign the right sub­tree to root.

NOTE: This prob­lem is very smililar to ” Given a Sorted Array, Con­vert it into its Bal­anced Binary search TreeandCon­vert a Sorted Dou­bly Linked List to Bal­anced BST” .

Com­plete Code:

Out­put:

`Constructed BST is : 1 2 3 4 5 6`