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.

Use this node definition to create the program

 typedef struct node { 

int data;

 struct node *left, *right; } node; 

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 are below.

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.

**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.