# Sorted Linked List to Balanced BST

Moderate
0/80
Average time to solve is 25m
Contributed by

## Problem statement

You have been given a singly linked list in which nodes are present in increasing order. Your task is to construct a Balanced Binary Search Tree with the same data elements as the given Linked List.

A Balanced BST is defined as a BST in which the height of two subtrees of every node differs no more than 1.

Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 100
0 <= N <= 1000
1 <= Data <= 10^9
Data != -1

Time Limit: 1sec
``````
##### Sample Input 1 :
``````2
1 2 3 4 5 -1
5 7 8 -1
``````
##### Sample Output 1:
``````3 2 5 1 -1 4 -1 -1 -1 -1 -1
7 5 8 -1 -1 -1 -1
``````
##### Explanation for Sample Input 1:
``````Test Case 1: The balanced BST corresponding to the linked list is-
``````

``````Level order traversal of above BST is 3 2 5 1 -1 4 -1 -1 -1 -1 -1

Test Case 2: The balanced BST corresponding to the linked list is-
``````

``````Level order traversal of above BST is 7 5 8 -1 -1 -1 -1
``````
##### Sample Input 2 :
``````2
10 12 14 16 -1
-1
``````
##### Sample Output 2 :
``````12 10 14 -1 -1 -1 16 -1 -1
-1
``````
Console