69. Convert Sorted Singly Linked List to Balanced Binary Search Tree

Objective: You have been given a sorted singly List, you need to convert it into a balanced binary search tree.

Why a balanced binary tree is important:

You can also create the first node as root and insert all other nodes to the right of the tree because the List is in increasing order but this constructed tree won't be balanced, it will be the skewed tree and to perform operations on this tree will be O(n), not O(logn).

Example:

Approach:

• Say mid is the middle node in the linked list.
• Recursively construct left subtree from start to mid-1
• Make the middle node as root and assign the left subtree to it.
• Recursively construct the right subtree from mid+1 to end.
• Assign the right subtree to the root.

Output:

Constructed BST is : 1 2 3 4 5 6

NOTE: Similar problems " Given a Sorted Array, Convert it into its Balanced Binary search Tree" and Convert a Sorted Doubly Linked List to Balanced BST

Related Problems:

- Given an array, print all unique subsets with a given sum. Medium
- Get the Height of a Node in a Binary Tree Medium
- Binary Search Tree (BST) Complete Implementation. Beginner