CS 14 - List/Tree Recursion

List/Tree Recursion

30 points, Target Date: July 19 11:59pm

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

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

Hints

This program requires some serious 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.

Make sure you thoroughly test each function you implement.