Sorted Linked List to Balanced BST Problem Statement
Given a singly linked list where nodes contain values in increasing order, your task is to convert it into a Balanced Binary Search Tree (BST) using the same data values.
A Balanced BST is defined as a tree where the height of the two subtrees of any node differ by no more than 1.
Input:
The first line of input contains an integer T
denoting the number of test cases. Each test case is represented by a single line containing the elements of the linked list, separated by spaces and ending with -1. The value -1 is not a part of the list elements.
Output:
For each test case, output the values of the BST nodes in level order traversal, separated by spaces. Use -1 to represent NULL nodes where applicable. Ensure each test case's output is on a new line.
Example:
Consider the following Binary Search Tree representation:
Output for the above BST will be: 12 10 14 -1 -1 -1 16 -1 -1
Explanation:
Level 1: The root node of the tree is 12
Level 2: Left child of 12 = 10; Right child of 12 = 14
Level 3: Null children (-1) for all except 14, which has a right child 16
Level 4: Null children (-1) for node 16
During output representation, after printing each level's nodes, -1 should be used for non-existing (NULL) children, and the process continues until the last level where all nodes are null (-1).
Constraints:
1 ≤ T ≤ 100
0 ≤ N ≤ 1000
1 ≤ Data ≤ 10^9
- Data never equals -1
- Time Limit: 1 sec
Convert a sorted linked list into a Balanced Binary Search Tree (BST) using the same data values.
Create a function to convert the linked list to a BST by recursively dividing the list into halves
Maint...read more
Top TCS iON Technical Trainee interview questions & answers
Popular interview questions of Technical Trainee
Reviews
Interviews
Salaries
Users/Month