1. (100 pts) 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
4
6
8
10
12
14
16
Figure 1: Doubly-linked List
The binary search tree that is output of this process is
10
6 14
4
8
12
16
Figure 2: Binary Search Tree
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.
Sample execution of the program is given below
fox01 assign3
Enter numbers for doubly linked list in sorted order 4 6 8 10 12 14 16
Doubly Linked List Contents:
4 6 8 10 12 14 16
Binary Search Tree Contents:
4 6 8 10 12 14 16
