# [C++ FAST MONEY] Collecting Data in a Binary Tree [EASY]

Closed - This job posting has been filled and work has been completed.

## Job Description

In this Lab you will create a Data Structure to collect statistics from a series of Yes/No (True/False) questions. You will store the results in a full binary tree.

Each node of the binary tree will contain a string which is either a question (if it is an internal node) or a category (if it is a leaf node). An internal node will have two sub-trees, one for each response: yes or no. Answering questions will eventually lead to assigning a category to a respondent.

(NOTE: Example is in the attached document)

*** TASK #1: CREATING THE BINARY TREE ***
To build the tree, you must create binary nodes for each question and connect them with their left and right children. The children will be more binary nodes: either another question or a category.

You should create a menu system for building the binary tree. One way to do this is to write a recursive function which does the following:

1. Give the user a choice between creating a Question or a Category.
2. Read the question/category label into a string.
3. Create a new binary node to represent the question/category.
4. If the node is a Question (i.e.: it is an internal node), start again from step 1 for the yes branch and then again from step 1 for the no branch.
5. If the node is a Category (i.e.: it is a leaf), you are done.

Advice: your recursive function should have a BinNode* for a return value. You should start by writing a non- recursive function that correctly creates a new node (by asking the user for the needed information) and returns it. After this is done, you can add the recursive calls.

Example (partial construction of the above tree):

Building Binary Tree:
=========================================

[1] New Question
[2] New Category
>1
Enter Question> Is it morning?

Answer is "yes" to question "Is it morning?"
-----------------------------------------
[1] New Question
[2] New Category
>1
Enter Question> Are you tired?

Answer is "yes" to question "Are you tired?"
-----------------------------------------
[1] New Question
[2] New Category
>1
Enter Question> Are you very tired?

Answer is "yes" to question "Are you very tired?"
-----------------------------------------
[1] New Question
[2] New Category
>2
Enter Category> Coffee

Answer is "no" to question "Are you very tired?"
-----------------------------------------
[1] New Question
[2] New Category
>2
Enter Category> Tea

Answer is "no" to question "Are you tired?"
-----------------------------------------
[1] New Question
[2] New Category
>2
Enter Category> Orange Juice
...

*** TASK #2: PRETTY PRINT THE BINARY TREE ***
Write a recursive function to "pretty print" your binary tree. For the example:

Is it the morning?
Are you tired?
Are you very tired?
[Coffee]
[Tea]
[Orange Juice]
Do you drink alcohol?
Do you prefer wine?
[Red Wine]
[Beer]
Do you prefer sweet drinks?
[Soft Drink]
[Water]

1. If the node is a leaf (category), stop the questions and record the result.
3. If the answer is "yes", perform the right sub-tree.
4. If the answer is "no", perform the left sub-tree.

An example:
Is it the morning? yes
Are you tired? yes
Are you very tired? yes
Coffee

*** TASK #4: COMPILING STATISTICS ***
You are to print out how many respondents fall into each category. To do this you must traverse the tree and output the data from each leaf node. Give the number of people in each category as well as the percent out of the total number of respondents. (The order of the categories isn't important, as long as they are all present in the output).

Water: 10 (15.8%)
Soft Drink: 5 (7.9%)
Beer: 12 (19.0%)
Red Wine: 10 (15.8%)
Orange Juice: 4 (6.3%)
Tea: 2 (3.2%)
Coffee: 20 (31.7%)

*** REQUIREMENTS ***
1) Upon starting, your program should begin construction of a binary tree.
2) After the tree is built you should have a main menu from which you will run the operations in Tasks #2, #3 and #4:

[1] Display Tree
[3] Print Category Stats

3) Your full binary tree data structure should be implemented as a class.