//
// balancebst.cpp
//

#include <iostream>
#include <queue>
#include "bst.h"
// #include "mergeSort.h"

using namespace main_savitch_10;
using namespace std;

template <class Item>
void copyQueueToArray(queue<Item>& q, Item A[])
{
	int queueSize = q.size();
	for (int i = 0; i < queueSize; i++) {
		A[i] = q.front();
		q.pop();
	}
}

template <class Item>
void bst_copyToQueue(const binary_tree_node<Item>* node_ptr, queue<Item>& q)
{
	if (node_ptr == NULL) 
		return;

	bst_copyToQueue(node_ptr->left(), q);
	q.push(node_ptr->data());
	bst_copyToQueue(node_ptr->right(), q);
	return;
}

//
// *** Your implementation of the function bst_copyFromArray will go here.
//

template <class Item>
binary_tree_node<Item>* bst_rebalance(const binary_tree_node<Item>* node_ptr)
{
	queue<char> q;
	bst_copyToQueue(node_ptr, q);

	int numberOfNodes = q.size();
	char* A = new char[numberOfNodes];
	copyQueueToArray(q, A);

	binary_tree_node<Item>* temp_ptr = NULL;
	bst_copyFromArray(temp_ptr, A, 0, numberOfNodes - 1);
	return temp_ptr;
}

int main()
{
	binary_tree_node<char>* root_ptr = NULL, *temp_ptr = NULL;

	bst_insert(root_ptr, 'a');

	bst_insert(root_ptr, 'b');
	bst_insert(root_ptr, 'c');
	
	bst_insert(root_ptr, 'd');
	bst_insert(root_ptr, 'e');
	bst_insert(root_ptr, 'f');

	bst_insert(root_ptr, 'g');
	bst_insert(root_ptr, 'h');
	
	cout << "Original tree: " << endl;
	print(root_ptr, 7);

	temp_ptr = root_ptr;
	root_ptr = bst_rebalance(root_ptr);
	tree_clear(temp_ptr);
	temp_ptr = NULL;
	cout << "Rebalanced tree: " << endl;
	print(root_ptr, 7);

	return 0;
}