[Solved] Programming Assignment #4: Reflections and Kindred Spirits

This program is designed to get you thinking recursively with binarytrees. Rather than solving one big problem, you will code up solutions tothree smaller problems, each of which will rely on recursion to somedegree.This time around, I’m not giving you a slew of function definitions thatessentially pre-define the structure of your program. Accordingly, thisassignment will challenge you to think creatively, both in terms of how tosolve the problems, as well as how to make appropriate use of helperfunctions as you plan out how to structure your code – especially with thekindredSpirits() function. This will be fun.AttachmentsKindredSpirits.h, testcase{01-16}.c, output{01-16}.c, and test-all.shDeliverablesKindredSpirits.c(Note! Capitalization of your filename matters!)1. Overview, Part 1 of 2: ReflectionsGiven two binary trees, we say that one is a reflection of the other if they are symmetric in terms ofboth their structure and their node values. For example, the following trees are reflections of oneanother:Figure 1: Two trees that are reflections of one another.The following trees are not reflections of one another, because although they are symmetric images ofone another structurally, they are not symmetric in terms of their values:Figure 2: Two structurally symmetric trees that are not reflections of one anotherbecause they are lack symmetry with respect to their node values.Because the following binary trees are not structurally symmetric (and therefore they also cannot besymmetric in terms of the values contained in each node), they are not reflections of one another:Figure 3: Structurally asymmetric trees cannot be reflections of one another.1020 3040 11030 201 401030 2040 11030 201 401816 5133 191816 513319The following binary trees are reflections of one another:Figure. 4: Two trees that are reflections of one another. They areperfect binary trees. They are also large and in charge.Recall that the tree above is a perfect binary tree. You might ask yourself, “Is it always the case that aperfect binary tree is a reflection of itself?” The answer is, “No!” Here’s a counterexample that showsthat a perfect binary tree is not always a reflection of itself:Figure 5: This perfect binary tree is not a reflection of itself. Despite itsstructural symmetry, it is not symmetric to itself with respect to its node values.Any binary tree with a single node is a reflection of itself. For example:Figure 6: Two trees that are reflections of one another.However, it is not the case that all binary trees with a single node are reflections of one another. Forexample:Figure 7: Two trees that are not reflections of one another, becausethey are not symmetric with respect to their values.214 143462 62 62 6234 34 34 34 34 34 34214 143462 62 62 6234 34 34 34 34 34 3438170 473 5 938170 473 5 933 3315 21Finally, note that the empty tree is a reflection of itself:Figure 8: Two trees (both empty) that are reflections of one another.This example is serene and beautiful, and brings with it an overwhelmingsense that everything is going to be okay.2. Overview, Part 2 of 2: Kindred SpiritsWe say that two binary trees are kindred spirits if the preorder traversal of one of the trees correspondsto the postorder traversal of the other tree. For example, the following trees are kindred spirits:Figure 9: These trees are kindred spirits. The preorder traversal of thetree on the left is 23, 12, 5, 18, 71, 56, which corresponds to the postordertraversal of the tree on the right.Note that the trees above are still kindred spirits even if we swap their order:Figure 10: These trees from Figure 9 are still kindred spirits, despite the factthat the preorder traversal of the tree on the right now matches the postordertraversal of the tree on the left, instead of the other way around.2312 715 18 565623 715 18122312 715 18 565623 715 18123. Binary Tree Node Struct (KindredSpirits.h)You must use the node struct we have specified in KindredSpirits.h without any modifications. Youwill have to #include the header file in your KindredSpirits.c source file like so:#include “KindredSpirits.h”Note that the capitalization of KindredSpirits.c matters! Filenames are case sensitive in Linux, andthat is of course the operating system we’ll be using to test your code.The node struct is defined in KindredSpirits.h as follows:typedef struct node{int data;struct node *left, *right;} node;If you’re using Code::Blocks, you will need to add the KindredSpirits.h header file to your project.See the instructions in Section 8, “Compilation and Testing (Code::Blocks).”4. Test Cases and the test-all.sh ScriptAs always, I’ve included several test cases, which show some ways in which I might test your code.These test cases are not comprehensive. You should also create your own test cases if you want to testyour code comprehensively.I’ve included a script, test-all.sh, that will compile and run all test cases for you. You can run it onEustis by placing it in a directory with KindredSpirits.c and KindredSpirits.h and typing:bash test-all.sh5. OutputThe functions you write for this assignment should not produce any output. If your functions causeanything to print to the screen, it might interfere with our test case evaluation. Be sure to disable orremove any printf() statements you have in your code before submitting this assignment.6. Function RequirementsYou have a lot of leeway with how to approach this assignment. There are only five required functions,and you may write helper functions as you see fit. For the kindredSpirits() function, you will likelyneed quite a few helper functions, and a good measure of creative thinking and/or cleverness.Function descriptions for this assignment are included on the following page. Please do not include amain() function in your submission.int isReflection(node *a, node *b);Description: A function to determine whether the trees rooted at a and b are reflections of oneanother, according to the definition of “reflection” given above. This must be implementedrecursively.Returns: 1 if the trees are reflections of one another, 0 otherwise.node *makeReflection(node *root);Description: A function that creates a new tree, which is a reflection of the tree rooted at root.This function must create an entirely new tree in memory. As your function creates a new tree,it must not destroy or alter the structure or values in the tree that was passed to it as a parameter.Tampering with the tree rooted at root will cause test case failure.Returns: A pointer to the root of the new tree. (This implies, of course, that all the nodes in thenew tree must be dynamically allocated.)int kindredSpirits(node *a, node *b);Description: A function that determines whether the trees rooted at a and b are kindred spirits.(See definition of “kindred spirits” above.) The function must not destroy or alter the trees inany way. Tampering with these trees will cause test case failure.Special Restrictions: To be eligible for credit, the worst-case runtime of this function cannotexceed O(n), where n is the number of nodes in the larger of the two trees being compared. Thisfunction must also be able to handle arbitrarily large trees. (So, do not write a function that hasa limit as to how many nodes it can handle.) You may write helper functions as needed.Returns: 1 if the trees are kindred spirits, 0 otherwise.double difficultyRating(void);Returns: A double indicating how difficult you found this assignment on a scale of 1.0(ridiculously easy) through 5.0 (insanely difficult).double hoursSpent(void);Returns: An estimate (greater than zero) of the number of hours you spent on thisassignment.The remaining pages of this document contain compilation instructions for Linux/Mac(pg. 7) and Windows (pg. 8), further restrictions and guidelines for your program (seepgs. 8 and 9), and grading criteria (pg. 9).7. Compilation and Testing (Linux/Mac Command Line)To compile multiple source files (.c files) at the command line:gcc KindredSpirits.c testcase01.cBy default, this will produce an executable file called a.out, which you can run by typing:./a.outIf you want to name the executable file something else, use:gcc KindredSpirits.c testcase01.c -o KindredSpirits.exe…and then run the program using:./KindredSpirits.exeRunning the program could potentially dump a lot of output to the screen. If you want to redirect youroutput to a text file in Linux, it’s easy. Just run the program using the following command, which willcreate a file called whatever.txt that contains the output from your program:./KindredSpirits.exe > whatever.txtLinux has a helpful command called diff for comparing the contents of two files, which is reallyhelpful here since we’ve provided several sample output files. You can see whether your outputmatches ours exactly by typing, e.g.:diff whatever.txt output01.txtIf the contents of whatever.txt and output01.txt are exactly the same, diff won’t have any output.It will just look like this:[email protected]:~$ diff whatever.txt output01.txt[email protected]:~$ _If the files differ, it will spit out some information about the lines that aren’t the same. For example:[email protected]:~$ diff whatever.txt output01.txt1c1< fail whale 🙁—> Success![email protected]:~$ _8. Compilation and Testing (Code::Blocks)The key to getting your program to include a custom header file in Code::Blocks (or any IDE) is tocreate a project. Here are the step-by-step instructions for creating a project in Code::Blocks, importingKindredSpirits.h and the KindredSpirits.c file you’ve created (even if it’s just an empty file so far).1. Start Code::Blocks.2. Create a New Project (File → New → Project).3. Choose “Empty Project” and click “Go.”4. In the Project Wizard that opens, click “Next.”5. Input a title for your project (e.g., “KindredSpirits”).6. Pause to reflect on life a bit. Isn’t this amazing?7. Choose a folder (e.g., Desktop) where Code::Blocks can create a subdirectory for the project.8. Click “Finish.”Now you need to import your files. You have two options:1. Drag your source and header files into Code::Blocks. Then right click the tab for each file andchoose “Add file to active project.”– or –2. Go to Project → Add Files…. Then browse to the directory with the source and header files youwant to import. Select the files from the list (using CTRL-click to select multiple files). Click“Open.” In the dialog box that pops up, click “OK.”You should now be good to go. Try to build and run the project (F9). As a friendly reminder: Even ifyou develop your code with Code::Blocks on Windows, you ultimately have to transfer it to the Eustisserver to compile and test it there. See the following page (Section 7, “Compilation and Testing(Linux/Mac Command Line)”) for instructions on command line compilation in Linux.9. DeliverablesSubmit a single source file, named KindredSpirits.c, via Webcourses. The source file should containdefinitions for all the required functions (listed above), as well as any auxiliary functions you need tomake them work. Don’t forget to #include “KindredSpirits.h” in your source code. Your programshould compile on Eustis with both of the following :gcc -c KindredSpirits.cgcc KindredSpirits.c testcase01.c10.Special Restrictions1. As always, you must avoid the use of global variables, mid-function variable declarations, andsystem calls (such as system(“pause”)).2. Do not submit the KindredSpirits.h header file with your code. You should only submitKindredSpirits.c. We will use our own version of the header file when testing your program.3. Be sure you don’t write anything in KindredSpirits.c that conflicts with what’s given inKindredSpirits.h. Namely, do not try to define a node struct in KindredSpirits.c, sinceyour source file will already be importing the definition of a node struct fromKindredSpirits.h.4. Be sure to include your name and NID as a comment at the top of your source file.5. No shenanigans. For example, if you write a kindredSpirits() function that always returns 1,you might not receive any credit for the test cases that it happens to pass.6. Your KindredSpirits.c file must not include a main() function. If it does, your code will failto compile during testing, and you will not receive credit for this assignment.11.GradingThe expected scoring breakdown for this programming assignment is:80% Correct output for test cases used in grading10% Appropriate use of functional decomposition10% Comments and whitespaceNote! Your program must be submitted via Webcourses, and it must compile and run on Eustis toreceive credit. Programs that do not compile will receive an automatic zero.Your grade will be based primarily on your program’s ability to compile and produce the exact resultsexpected. Even minor deviations will cause your program’s output to be marked as incorrect, resultingin severe point deductions. The same is true of how you name your functions and their parameters.Please be sure to follow all requirements carefully and test your program thoroughly.Note also that your functions should not print anything to the screen. If they do, it will interfere withthe output we generate while testing, resulting in incorrect test case results and an unfortunate loss ofpoints.Additional points will be awarded for style (commenting and whitespace practices) and functionaldecomposition (i.e., don’t write a 300-line kindredSpirits() function; break it up into meaningfulfunctions!). The graders will inspect your isReflection() and kindredSpirits() functions toensure they aren’t just bogus functions that always returns 1. Shenanigans like that might result insevere point deductions. Also, don’t forget that the runtime of kindredSpirits() should not exceedO(n), where n is the number of nodes in the larger of the two trees being compared.