datastructure.hpp

/* * DO NOT CHANGE THIS FILE */ #include  #include  #include  using namespace std; typedef struct TreeNode { int key; int val; bool flag; int num_children; TreeNode **children; } TreeNode; class Tree { protected: TreeNode* root; int max_width; public: Tree(int width); int get_height(); string left_view(); string right_view(); void insert_node(int key, int val); void delete_node(int val); static void solution(const char *input_path, const char *output_path); }; 

main.cpp

/* * DO NOT CHANGE THIS FILE! * */ #include  #include  #include  using namespace std; int main(int argc, char const *argv[]) { // ./main linked_list [INPUT_FILE] [OUTPUT_FILE] if (argc != 4) { cout  

tree.cpp

#include "datastructure.hpp" #include  #include  #include  Tree::Tree(int width){ root = NULL; max_width = width; } int Tree::get_height(){ } string Tree::left_view(){ } string Tree::right_view(){ } //HELP WITH THIS FUNCTION: Insert node in tree void Tree::insert_node(int key, int val){ //created node TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->key = key; newNode->val = val; //insert node if(root==NULL){ root = newNode; return root; } //use queue for level order traversal } void Tree::delete_node(int val){ } void Tree::solution(const char *input_path, const char *output_path){ //To read input files: No need to change ifstream input_file(input_path); ofstream output_file(output_path); string line; int num, num1, num2; vector  ilist;\ while (getline(input_file, line)) { if (line.at(0) == 't'){ stringstream ss; ss > temp; if (stringstream(temp) >> num) temp = ""; } Tree t(num); TreeNode.num_children = 0; } if (line.at(0) == 'i'){ stringstream ss; ss > temp; if (stringstream(temp) >> num) temp = ""; ilist.push_back(num); } num1 = ilist[1]; num2 = ilist[2]; t.insert_node(num1, num2); } } }

input file

t 4 c the tree will have at most four children i 1 1 h l i 2 2 i 3 2 i 4 2 i 5 2 h l

Homework Content You don't have to worry about edge cases other than decribed in each section. 1. Each Node in TreeNode will have unique trees. But value can duplicate. 2. An empty tree has height 0. A tree with only a root node has height 1. Tree You will find the input file for stack in [PROJ_ROOT]/input/tree/[num].txt. For each line in the input file for binary search tree: 1. c COMMENTS All comments will begin with c. 2. tw Create an empty tree. Note there will be only one t for every file and t will always proceed other non- comment commands. w defines the width of the tree. 3. ik v Create a tree node with key = k and value = v insert the new node into the tree. (See Example Below] (#Tree Insertion) 4. i Print the left view of the tree. (See Example Below](#Tree Views) 5. r Print the right view of the tree (See Example Below](#Treel Views) 6. d v Delete the subtree if the subtree root's value is v [See Example Below](#Tree Deletion) Homework Content You don't have to worry about edge cases other than decribed in each section. 1. Each Node in TreeNode will have unique trees. But value can duplicate. 2. An empty tree has height 0. A tree with only a root node has height 1. Tree You will find the input file for stack in [PROJ_ROOT]/input/tree/[num].txt. For each line in the input file for binary search tree: 1. c COMMENTS All comments will begin with c. 2. tw Create an empty tree. Note there will be only one t for every file and t will always proceed other non- comment commands. w defines the width of the tree. 3. ik v Create a tree node with key = k and value = v insert the new node into the tree. (See Example Below] (#Tree Insertion) 4. i Print the left view of the tree. (See Example Below](#Tree Views) 5. r Print the right view of the tree (See Example Below](#Treel Views) 6. d v Delete the subtree if the subtree root's value is v [See Example Below](#Tree Deletion)