1. Write a program to convert a sorted double-linked list to a binary search tree. You can only change the target of pointers, but cannot create any new nodes. Use previous node in doubly-linked list as left pointer of binary search tree and next node in doubly-linked list as right pointer of binary search tree.
Consider the double-linked list given below
The binary search tree that is output of this process is
It will be easier to write this program using recursion. Find the middle node in the doubly linked list and set it as root, convert the left sublist and set it as left subtree, convert the right sublist and set it as right subtree. Test your program with different doubly linked lists. To test your binary search tree, you can print the contents.
