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

Problem

Submissions

Hints & solutions

Discuss

Sorted Linked List to Balanced BST

Moderate

0/80

Average time to solve is 25m

Contributed by

30 upvotes

Asked in companies

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 )

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The only line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print the nodes of the tree in the level order form separated by single spaces (Print -1 for NULL nodes). Refer to the below example for further clarification.

Print the output for every test case in a separate line.

For Example

Consider the Binary Search Tree-

The above BST will be printed as-
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 :
Left child of 10 = null(-1)
Right child of 10 = null (-1)
Left child of 14 = null(-1)
Right child of 16 = 16

Level 4 :
Left child of 16 = null (-1)
Right child of 16 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The output for each test case ends when all nodes at the last level are null (-1).

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

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

Hint 1

Hint 2

As the binary tree would be balanced, think about finding the root of the BST, and then compute recursively.

Approaches (2)

Approach 1

Approach 2

Recursion

The key observation here is that the middle node of the linked list would be the root of the BST. Therefore the nodes which lie to the left of the middle node will necessarily form the left subtree of the BST and which lies right to it will form the right subtree. So, we will devise a recursive solution based on this observation.

Algorithm

We will keep the head pointer of the linked list as one of our parameters of the recursion function.
We will find the pointer to the middle node of the linked list by the standard two pointers approach.
- The data of this node will be copied to the current root of the subtree.
- Let the previous pointer to the middle node be prev. We will set prev -> next = NULL.
We will recurse on the left half of this linked list and by passing the head pointer as our parameter. This will necessarily become the left subtree of the current root node.
We will recurse on the right half of the linked list by passing the middle -> next pointer as our parameter. This will necessarily become the right subtree of the current root node.

Time Complexity

O(NlogN), where N denotes the number of nodes in the BST.

As the binary tree is balanced, its height will be at most logN. As for every level of the BST, we are iterating over the complete linked list to find the middle element, the time complexity will be O(NlogN).

Space Complexity

O(logN), where N denotes the number of nodes in the binary tree.

As the binary tree is balanced, its height will be at most logN. So the size of the recursive stack will be at most logN.

(100% EXP penalty)

Sorted Linked List to Balanced BST

SHAIKH IRFAN

Interview problems

Sorted Linked List to Balanced BST(99.44%)

import java.util.*;

public class Solution

{

public static TreeNode<Integer> find(ArrayList<Integer> list,int i,int j){

if(i > j)return null;

int mid = i+(j-i)/2;

TreeNode<Integer> root = new TreeNode<Integer>(list.get(mid));

root.left = find(list, i, mid-1);

root.right = find(list, mid+1, j);

return root;

}

public static TreeNode<Integer> sortedListToBST(Node<Integer> head)

{

// Write your code here.

ArrayList<Integer> list = new ArrayList<>();

Node<Integer> temp = head;

while(temp != null){

list.add(temp.data);

temp = temp.next;

}

return find(list,0,list.size()-1);

}

113 views

0 replies

1 upvote

Somya Singh

Interview problems

Java Solution|Tc-O(n)

ArrayList<Integer> list = new ArrayList<>();
		Node<Integer> temp = head;
		while(temp != null){
			list.add(temp.data);
			temp = temp.next;
		}
		int n = list.size();
		return sortedListToBSTUtil(list, 0, n-1);
	}
	public static TreeNode sortedListToBSTUtil(List<Integer> list, int start, int end){
		if(start > end) return null;
		int mid = start + (end - start)/2;
		TreeNode<Integer> root = new TreeNode<Integer>(list.get(mid));
		root.left = sortedListToBSTUtil(list,start,mid-1);
		root.right =  sortedListToBSTUtil(list,mid+1, end);
		return root;
	}

15 views

0 replies

0 upvotes

Manish Soni

Interview problems

C++ Sol

int countNodes(Node<int>*head){

Node<int>*temp=head;

int cnt=0;

while(temp!=NULL){

cnt++;

temp=temp->next;

}

return cnt;

}

TreeNode<int>* solve(Node<int>*&head,int n){

if(head==NULL || n<=0){

return NULL;

}

TreeNode<int>* left=solve(head,n/2);

TreeNode<int>*root=new TreeNode<int>(head->data);

head=head->next;

root->left=left;

root->right=solve(head,n-1-n/2);

return root;

}

TreeNode<int>* sortedListToBST(Node<int>* head)

{

if(head==NULL){

return NULL;

}

int n=countNodes(head);

return solve(head,n);

}

59 views

0 replies

0 upvotes

Shubham kumar

Interview problems

C++ || Optimised approach

// Optimised appraoch

int countNodes(Node<int> *head){

if(!head)

return 0;

return 1 + countNodes(head->next);

}

TreeNode<int> *BuildTree(Node<int>* &head, int n){

// Base case

if(!head || n<=0)

return NULL;

// Build the left Subtree

TreeNode<int> *left = BuildTree(head, n/2);

// Create the root node

TreeNode<int> *root = new TreeNode<int>(head->data);

head = head->next;

root->left = left;

// Build the right Subtree

root->right = BuildTree(head, n - 1 - n/2);

return root;

}

TreeNode<int>* sortedListToBST(Node<int>* head) {

int n = countNodes(head);

if(!head)

return NULL;

// Build the tree

return BuildTree(head, n);

}

51 views

0 replies

1 upvote

Shubham kumar

Interview problems

C++ || Without extra space T.C O(NLogN)

TreeNode<int>* sortedListToBST(Node<int>* head) {

if (!head)

return NULL;

if (!head->next)

return new TreeNode<int>(head->data);

// Find the mid of the LL

Node<int>* slowPrev = NULL;

Node<int>* slow = head;

Node<int>* fast = head;

while (fast && fast->next) {

slowPrev = slow;

slow = slow->next;

fast = fast->next->next;

}

// Slow is pointing to the mid of the LL now create the root node

TreeNode<int>* root = new TreeNode<int>(slow->data);

if (slowPrev)

slowPrev->next = NULL; // Break the connection between left part and root

// Create the left subtree

root->left = sortedListToBST(head);

// Create the right subtree

root->right = sortedListToBST(slow->next);

return root;

}

30 views

0 replies

1 upvote

IIT

Interview problems

Java Solution

import java.util.*;

public class Solution
{
	public static TreeNode<Integer> find(ArrayList<Integer> list,int i,int j){
		if(i > j)return null;
		int mid = i+(j-i)/2;
		TreeNode<Integer> root = new TreeNode<Integer>(list.get(mid));
		root.left = find(list, i, mid-1);
		root.right = find(list, mid+1, j);
		return root;
	}
	public static TreeNode<Integer> sortedListToBST(Node<Integer> head)
	{
		// Write your code here.
		ArrayList<Integer> list = new ArrayList<>();
		Node<Integer> temp = head;
		while(temp != null){
			list.add(temp.data);
			temp = temp.next;
		}
		return find(list,0,list.size()-1);
	}
}

23 views

0 replies

0 upvotes

Nilesh Keshavdas

Interview problems

Python Code without Space Complexity

Also Python interpretor has a problem change the TreeNode class with 

class TreeNode:
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None


def findMid(head):
	prev = None
	slow = head
	fast = head.next
	while(fast!=None and fast.next!=None):
		prev = slow
		slow = slow.next
		fast = fast.next.next
	return prev,slow
def sortedListToBST(head):
	if(head==None):
		return head
	if(head.next == None):
		return TreeNode(head.data)
	prev,mid = findMid(head)
	root = TreeNode(mid.data)
	if(prev!=None):
		prev.next = None
		root.left = sortedListToBST(head)
	else:
		root.left = None
	root.right = sortedListToBST(mid.next)
	return root

38 views

0 replies

0 upvotes

Sayan Saha

Interview problems

Java


import java.util.*;

public class Solution
{
	public static TreeNode<Integer> sortedListToBST(Node<Integer> head){
		List<Integer> treeData = new ArrayList<Integer>();
		Node<Integer> temp = head;
		while(temp != null){
			treeData.add(temp.data);
			temp = temp.next;
		}
		return _createBST(treeData, 0 , treeData.size() - 1);

	}
	public static TreeNode _createBST(List<Integer> treeData, int start, int end){
		
		if(start > end){
			return null;
		}

		int middle = start + (end - start) / 2;
		TreeNode<Integer> treeNode = new TreeNode(treeData.get(middle));
		treeNode.left = _createBST(treeData, start, middle - 1);
		treeNode.right = _createBST(treeData, middle + 1, end);

		return treeNode;

	}

}

44 views

0 replies

0 upvotes

Indrasen Chauhan

Interview problems

Using extra space O[n]

TreeNode<int>* recursion(int s, int e, vector<int> &nums){

if(s > e){

return NULL;

}

int mid = s + (e-s)/2;

TreeNode<int>* temp = new TreeNode<int>(nums[mid]);

temp->left = recursion(s, mid-1, nums);

temp->right = recursion(mid+1, e, nums);

return temp;

}

TreeNode<int>* sortedListToBST(Node<int>* head) {

vector<int> nums;

Node<int>* temp = head;

while(temp!= NULL){

nums.push_back(temp->data);

temp = temp->next;

}

return recursion(0, nums.size()-1, nums);

}

106 views

0 replies

1 upvote

Akshit Yadav

Interview problems

Java Recursive

public class Solution
{
	public static Node<Integer> getMid(Node<Integer> head) {
		if (head == null)
			return null;
		Node<Integer> slow = head, fast = head;

		while (fast!=null && fast.next!=null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	public static TreeNode<Integer> sortedListToBST(Node<Integer> head)
	{
		// Write your code here.
		if (head==null) {
			return null;
		}
		if (head.next==null) {
			TreeNode<Integer> root = new TreeNode<>(head.data);
			return root;
		}

		Node<Integer> mid = getMid(head);
		TreeNode<Integer> root = new TreeNode<>(mid.data);

		// separating the left, mid, right;
		Node<Integer> left = head, temp = head, right = mid.next;;
		while (temp.next!=mid) {
			temp = temp.next;
		}
		temp.next = null;

		TreeNode<Integer> leftST = sortedListToBST(left);
		TreeNode<Integer> rightST = sortedListToBST(right);

		root.left = leftST;
		root.right = rightST;

		return root;
	}
}

55 views

0 replies

0 upvotes

Console