CS 14 - List/Tree Recursion

CS 14 List/Tree Recursion

Your assignment is to write a function that takes a binary search tree and recursively changes the internal pointers to convert it into a circular, sorted, doubly-linked list. (A circular, sorted, doubly-linked list is a sorted doubly-linked list whose head and tail elements point at one another, but is sorted in increasing order otherwise.)

Details

Your function for the conversion is not allowed to allocate any additional nodes. This problem must be done "in place." (That is, if you allocate anything of type Node (instead of Node*) or call "new" you are doing it wrong.)

You will need to use the following structure for your tree/list nodes:

class Node
{
public:
    int val;
    Node* prev;
    Node* next;
};

A visual depiction of what you need to do:

(Note that the NULL pointers in the tree representation are not shown.)

To get full credit you must write a function Node* treeToList(Node* tree) that recursively performs the conversion. The Node* that it returns (the head of the circular, sorted, doubly-linked list) should be the MINIMUM element of the list.

We heartily suggest that you extensively test your function in your main(), but for testing we will be taking OUT your main function and replacing it with ours to ensure that your function is written correctly. Thus your function MUST have the same function signature.

Hints

This program requires some thought. Do not just start writing code. Figure out the recursion first.

You will want to write a function that takes in two circular, sorted, doubly-linked lists and merges them into one. This is in many ways the tough part of the assignment. Think about how you will be using this before you start writing it, this does not need to be completely general.

Make sure you thoroughly test each function you implement.