This program is designed to get you thinking recursively with binary trees. Rather than solving one big problem, you will code up solutions to three smaller problems, each of which will rely on recursion to some degree.
This time around, I'm not giving you a slew of function definitions that essentially pre-define the structure of your program. Accordingly, this assignment will challenge you to think creatively, both in terms of how to solve the problems, as well as how to make appropriate use of helper functions as you plan out how to structure your code - especially with the kindredSpirits() function. This will be fun.
Given two binary trees, we say that one is a reflection of the other if they are symmetric in terms of both their structure and their node values. For example, the following trees are reflections of one another:
Figure 1: Two trees that are reflections of one another. see image.
The following trees are not reflections of one another, because although they are symmetric images of one another structurally, they are not symmetric in terms of their values:
Figure 2: Two structurally symmetric trees that are not reflections of one another because they are lack symmetry with respect to their node values. see image.
Because the following binary trees are not structurally symmetric (and therefore they also cannot be symmetric 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. see image.
The following binary trees are reflections of one another:
Figure. 4: Two trees that are reflections of one another. They are perfect binary trees. They are also large and in charge. see image.
Recall that the tree above is a perfect binary tree. You might ask yourself, "Is it always the case that a perfect binary tree is a reflection of itself?" The answer is, No! Here's a counterexample that shows that a perfect binary tree is not always a reflection of itself:
Figure 5: This perfect binary tree is not a reflection of itself. Despite its structural symmetry, it is not symmetric to itself with respect to its node values. see image.
Any binary tree with a single node is a reflection of itself. For example:
Figure 6: Two trees that are reflections of one another. see image.
However, it is not the case that all binary trees with a single node are reflections of one another. For example:
Figure 7: Two trees that are not reflections of one another, because they are not symmetric with respect to their values. see image.
Finally, 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 overwhelming sense that everything is going to be okay.
We say that two binary trees are kindred spirits if the preorder traversal of one of the trees corresponds to 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 the tree on the left is 23, 12, 5, 18, 71, 56, which corresponds to the postorder traversal of the tree on the right. see image.
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 fact that the preorder traversal of the tree on the right now matches the postorder traversal of the tree on the left, instead of the other way around. see image.
You must use the node struct we have specified in KindredSpirits.h without any modifications. You must #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, and that 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; // each node holds a single integer
struct node *left, *right; // pointers to node's left and right children
} node;
The functions you write for this assignment should not produce any output. If your functions cause anything to print to the screen, it might interfere with our test case evaluation. Be sure to disable or remove any printf() statements you have in your code before submitting this assignment.
You 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 likely need 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 a main() 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 one another, according to the definition of "reflection" given above. This must be implemented recursively.
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 the new 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 in any way. Tampering with these trees will cause test case failure.
Special Restrictions: To be eligible for credit, the worst-case runtime of this function cannot exceed O(n), where n is the number of nodes in the larger of the two trees being compared. This function must also be able to handle arbitrarily large trees. (So, do not write a function that has a 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: A reasonable and realistic estimate (greater than zero) of the number of hours you spent on this assignment.