Assignment 3 Solution

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 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

 
Powered by