Convert a sorted Doubly Linked List to Balanced Binary Search Tree
Given a doubly linked list in sorted order with previous and next nodes. Convert the doubly linked list to a binary search tree with left as previous node and right as next node. Consider the list below:
The list should be converted to following BST:
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
We recursively traverse to the leaves and then create the tree upwards from the leaves to the root. Step 1. Calculate the length of the linked list. Step 2. Recursively create left sub tree from first half nodes. Step 3. Make middle node as the root and node returned from previous call (Step 2) as left child of the root. Step 4. Move head to next node. Step 5. Recursively create the right sub tree from second half nodes. Step 6. Return root.
Support us by whitelisting IDeserve in your ad-blocker.