CC150 4.4

4_4.cpp

/* CC150 4.4
 * Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth
 * (e.g., if you have a tree with depth D,you'll have D linked lists).
 */

#include "bstree.h" // https://gist.github.com/df2d3552fbe8c2342541
#include <list>
#include <vector>

using namespace std;

// Approach 1: use an array to hold the linked lists
int getHeight(Node *root) // get height of the binary tree
{
	if (root == nullptr)
		return 0;
	int lheight = getHeight(root->left);
	int rheight = getHeight(root->right);
	return lheight >= rheight ? lheight + 1 : rheight + 1;
}

void listInsert(Node *leaf, list<Node> *tlst, int level) // insert sub-tree with root leaf into corresponding lists
{
	if (leaf == nullptr)
		return;
	tlst[level].push_back(*leaf);
	listInsert(leaf->left, tlst, level + 1);
	listInsert(leaf->right, tlst, level + 1);
}

list<Node> *btreeToList(Node *root) // convert binary tree to array of linked lists
{
	if (root == nullptr)
		return nullptr;
	list<Node> *tlst = new list<Node>[getHeight(root)]; // initialize array of linked lists with size height
	listInsert(root, tlst, 0);
	return tlst;
}



// Approach 2: use a vector to hold the linked lists (don't need to know the tree height first).
void listInsert(Node *leaf, vector<list<Node>> &lists, int level)
{
	if (leaf == nullptr) // reach the bottom of the tree
		return;
	if (level == lists.size()) { // first time of a new level of the tree
		list<Node> newList;
		lists.push_back(newList);
	}
	lists[level].push_back(*leaf);
	listInsert(leaf->left, lists, level + 1);
	listInsert(leaf->right, lists, level + 1);
}

vector<list<Node>> btreeToListVec(Node *root)
{
	vector<list<Node>> lists;
	listInsert(root, lists, 0);
	return lists;
}

// Approach 3: perform BFS by level
vector<list<Node>> btreeToListBFS(Node *root)
{
	vector<list<Node>> lists;
	list<Node> currList; // temporary list to hold nodes of the current level
	if (root != nullptr)
		currList.push_back(*root);
	while (!currList.empty()) {
		lists.push_back(currList);
		vector<list<Node>>::iterator prev = --lists.end(); // iterator pointing at list of previous level
		currList.clear();
		for (auto begin = prev->begin(); begin != prev->end(); ++begin) {
			if (begin->left != nullptr)
				currList.push_back(*begin->left);
			if (begin->right != nullptr)
				currList.push_back(*begin->right);
			}
	}
	return lists;
}

void displayList(list<Node> *tlst, int size) // print each linked list in the array of given size
{
	for (int i = 0; i != size; ++i) {
		while (!tlst[i].empty()) {
			cout << tlst[i].front().data << " ";
			tlst[i].pop_front();
		}
		cout << endl;
	}
}

void displayListVec(vector<list<Node>> lists) // print each linked list in the vector
{
	for (auto list : lists) {
		while (!list.empty()) {
			cout << list.front().data << " ";
			list.pop_front();
		}
		cout << endl;
	}
}

int main()
{
	bstree bst; // create a binary search tree for test
	int key;
	while (cin >> key)
		bst.insert(key);
	int h = getHeight(bst.getRoot());
	cout << "Depth of tree: " << h << endl;
	cout << "DFS Using array: " << endl;
	list<Node> *bstList = btreeToList(bst.getRoot());
	displayList(bstList, h);
	cout << "DFS using vector: " << endl;
	vector<list<Node>> bstListVec = btreeToListVec(bst.getRoot());
	displayListVec(bstListVec);
	cout << "BFS using vector: " << endl;
	vector<list<Node>> bstListBFS = btreeToListBFS(bst.getRoot());
	displayListVec(bstListBFS);
	return 0;
}