Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Sorted Linked List to Balanced BST

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
27 upvotes
Asked in companies
AppleGoogleRed Hat

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-

alt text

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-

alt text

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
Full screen
Console