int compareTree(node *a, node *b); Description: A function that determines wheth
ID: 3731246 • Letter: I
Question
int compareTree(node *a, node *b);
Description: A function that determines whether the trees rooted at a and b are correspond. (Meaning; if the preorder traversal of one of the trees corresponds to the postorder traversal of the other tree) The function must not destroy or alter the trees in any way. Tampering with these trees will cause test case failure.
Special Restrictions: 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.
typedef struct node {
int data; struct node *left, *right;
} node;
in C
( Can use stacks and queues)
Explanation / Answer
//Using recursive stack
int compareTree(node* a, node* b)
{
if (a == NULL && b == NULL) {
return 1;
}
else if (a == NULL || b == NULL) {
return 0;
}
if (a->data == b.data) {
return compareTree(a->left, b->left) && compareTree(a->right, b->right);
}
return 0;
]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.