This post is completed by 2 users Login To Mark Completed

1

Add to List Add To List..(Max 5) Close Save

Medium

Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

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

Why 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 List is in increasing order but this constructed tree won't be a balanced tree, it will be the skewed tree and to perform operations on this tree will be O(n), not O(logn).

Input: An sorted Singly Linked List

Output: Balanced Binary Tree

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 root.

NOTE: This problem is very similar to " Given a Sorted Array, Convert it into its Balanced Binary search Tree" and Convert a Sorted Doubly Linked List to Balanced BST

Run This Code

Code:

Output:

Constructed BST is : 1 2 3 4 5 6

---

---

Also Read:

- Divide and Conquer - Rearrange array elements in special order Medium
- Find all subsets of size K from a given number N (1 to N) Medium
- Find the Deepest Left Node in a Binary Tree. Medium
- Construct a binary tree from given Inorder and Postorder Traversal Hard
- Find all unique combinations of exact K numbers (from 1 to 9 ) with sum to N Medium
- Collatz Conjecture - Steps to transform Number to 1 Beginner
- Dynamic Programming - Minimum Coin Change Problem Medium
- Backtracking - Knight's Tour Problem Hard

---