Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: You have been given a sorted singly List, you need to con­vert it into bal­anced binary search tree.

Why bal­anced binary tree is important:

You can also cre­ate first node as root and insert all other nodes to the right of the tree because List is in increas­ing order but this con­structed tree won’t be bal­anced tree, it wil be skwed tree and to per­form oper­a­tions on this tree will be O(n) not O(logn).

Input: An sorted Singly Linked List

Out­put: Bal­anced Binary Tree

Exam­ple:

Singly Linked List To BST

Singly Linked List To BST

Appraoch:

  • Say mid is the mid­dle node in the linked list.
  • Recur­sively con­struct left sub­tree from start to mid-1
  • Make the mid­dle node as root and assign the left sub­tree to it.
  • Recur­sively con­struct right sub­tree from mid+1 to end.
  • Assign the right sub­tree to root.

NOTE: This prob­lem is very smililar to ” Given a Sorted Array, Con­vert it into its Bal­anced Binary search TreeandCon­vert a Sorted Dou­bly Linked List to Bal­anced BST” .

Com­plete Code:


Out­put:

Constructed BST is : 1 2 3 4 5 6

You may also like...