# Assignment 3 Solution

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 diﬀerent 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

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 diﬀerent 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

You'll get a 1.3KB .ZIP file.