Preorder Binary Search Tree You will read numbers from a ?le to construct a binary search tree with them. Then you will output a representation of this BST to an output ?le using preorder traversal. The input ?le will consist of a single line of numbers separated by spaces. You may assume that there will always be less than 100 numbers and they will all be unique. Your C++ program must read these numbers in order and add them to a binary search tree with the ?rst number becoming the root node. You must implement a node and/or a binary tree class yourself. Implement these however you like but do not use advanced standard library features such as maps. Remember that there is no need to implement node deletion functionality you only need to implement add and traversal functions. For the output, the program will create a ?le with one line per node in preorder including the nodes location in the tree. For example, if the input ?le is: 3 1 2 4 Your program will:

• Read 3, making it the root node

• Read 1, go to the left child of 3, since the left child is empty insert 1 as left child of 3

• Read 2, go to the left child of 3, go to the right child of 1, since the right child is empty insert 2 as right child of 1

• Read 4, go to the right child of 3, since the right child is empty insert 4 as right child of 3

Then the binary tree stored in your program should be: The ?nal step of the program is to output this BST to a ?le. One way of representing a BST is by outputting its nodes through preorder traversal. Preorder traversal means: Access the current node. Traverse the left subtree by recursively calling the pre-order function. Traverse the right subtree by recursively calling the pre-order function. Then doing a preorder traversal on the previous BST will give: 3 1 2 4 To help visualize, lets also add the route you have to take to visit each node where x means root node, l means going to the left child and r means going to the right child. [x] 3 [xl] 1 [xlr] 2 [xr] 4 This is what the output ?le of your program should look like. It should contain one node per line outputted in preorder traversal and include the route you take during the traversal. The output ?le can be read as: 3 is at [x] so it is the root

2. is at [xl] so you have to go root->left to access it
4. is at [xlr] so you have to go root->left->right to access it 4 is at [xr] so you have to go root->right to access it input1.txt:

963254 1 BST in program: Expected output1.txt: [x] 9 [xl] 6 [xll] 3 [xlll] 2 [xllll] 1 [xllr] 5 [xllrl] 4 Important direction to submit your group assignment 3: We expect every student of a group will participate to solve the problem and discuss with each other. The purpose of this group assignment is to learn the basic functionality of binary search trees. If someone faces trouble understanding, they should discuss with their group members to get a clear understanding of the binary search trees. Every student of each group needs to submit the same copy of the solution. Group assignment 3 needs to be turned into the Linux server for this class. Make sure to create a folder under your root directory called ga3 (folder name must be in lower case and exactly written as ga3). Only copy your .cpp ?les, .h ?les, and ArgumentManager.h ?le to this folder, no test case ?les or other ?les are needed. Group assignments will be graded only once. You will not get the chance of resubmission after grading, so make sure you are submitting the correct solution before the due date. **Note: This document may contain typos. If anything seems illogical, please contact one of the TAs for clari?cation.