I am trying the implement a function which checks whether two binary search trees are equal, order of the nodes not matter. But my implementation does not work.
I am not allowed to flatten the trees into arrays.
this is what I have so far:
int isIdentical(struct Node* root1, struct Node* root2)
{
if (root1 == NULL && root2 == NULL)
return 1;
else if (root1 == NULL || root2 == NULL)
return 0;
else {
if (root1->data == root2->data && isIdentical(root1->left, root2->left)
&& isIdentical(root1->right, root2->right))
return 1;
else
return 0;
}
}
when supplied with trees containing the nodes tree A = 2 4 5 6 and Tree B = 2 5 4 6, the output should be:
1, meaning they are equal, but instead I am getting 0. I am not sure where I am going wrong.
This is how Node is implemeted:
struct Node {
int data;
struct Node* left;
struct Node* right;
};
CodePudding user response：
Make a recursive function that traverses treeA and checks that every item is present in treeB. On failure it abandons the search and returns 0 for failure. It can be your function
int isIdentical(struct Node* root1, struct Node* root2)
If success, call the function again with the arguments for treeA and treeB reversed. The 'check if present' operation can be iterative and inline, because it does not need to backtrack.
Example untried code, to give the idea.
int isAllFound(struct Node* root1, struct Node* root2)
{
// recursive parse of tree 1
if (root1 == NULL)
return 1;
// iterative search of tree 2
int found = 0;
struct Node *root = root2;
while(root != NULL) {
if(root1->data == root->data) {
found = 1;
break;
}
if(root1->data < root->data)
root = root->left;
else
root = root->right;
}
if(!found)
return 0;
// continue recursive parse of tree 1
if(!isAllFound(root1->left, root2))
return 0;
if(!isAllFound(root1->right, root2))
return 0;
return 1;
}
Then call like
if(isAllFound(treeA, treeB) && isAllFound(treeB, treeA))
puts("Success!");
If every item of treeA can be found in treeB, and every item of treeB can be found in treeA then they contain the same data. Provided the keys are unique.
CodePudding user response：
Why do you think they are equal? They are not.
tree A is represented as 2 4 5 6 which I guess you obtained by some sort of pre-order or level-order traversal. If your tree B (2, 5, 4, 6) is equal then with the same sort of traversal you'd obtain same order. They are not equal if the traversal is the same.
Order of nodes doesn't matter:
If the order of the nodes doesn't matter. One thing you could do is do an inorder traversal for both trees and you get a sorted array from both. Then compare both arrays element by element and declare equal or not.
CodePudding user response：
Your function will only compare as equal 2 trees that have exactly the same structure. If the trees are balanced differently, the comparison will return 0 even if the values are identical.
Performing this comparison is non trivial as the trees can have an arbitrary depth if they are not balanced.
You can walk the first tree in depth first order to populate an array and then walk the second tree in depth first order, checking that the values are identical to those in the array.
Here is a simple implementation:
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
size_t tree_length(const struct Node *root) {
return root ? 1 tree_length(root->left) tree_length(root->right) : 0;
}
void tree_store(int *array, size_t *pos, struct Node *node) {
if (node) {
tree_store(array, pos, node->left);
array[ *pos - 1] = node->data;
tree_store(array, pos, node->right);
}
}
int tree_check(int *array, size_t *pos, struct Node *node) {
if (node) {
return tree_check(array, pos, node->left)
&& array[ *pos - 1] == node->data
&& tree_check(array, pos, node->right);
} else {
return 1;
}
}
/* compare trees: return 0 if different, 1 if same values, -1 if allocation error */
int isIdentical(const struct Node *root1, const struct Node *root2) {
size_t len1 = tree_length(root1);
size_t len2 = tree_length(root2);
size_t pos;
if (len1 != len2)
return 0;
if (len1 == 0)
return 1;
int *array = malloc(sizeof(*array) * len1);
if (!array)
return -1;
pos = 0;
tree_store(array, &pos, root1);
pos = 0;
int res = tree_check(array, &pos, root2);
free(array);
return res;
}
If you are not allowed to convert the trees to arrays, you could:
- normalize both trees, then use your simple comparator, but this will modify the trees and is difficult.
- implement a stack based iterator and iterate both trees in parallel.
Here is a simple implementation of the latter:
#include <stddef.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
size_t max_size(size_t a, size_t b) {
return a < b ? b : a;
}
size_t tree_depth(const struct Node *root) {
return root ? 1 max_size(tree_depth(root->left), tree_depth(root->right)) : 0;
}
int tree_next(const struct Node **stack, size_t *ppos, int *value) {
size_t pos = *ppos;
if (stack[pos] == NULL) {
if (pos == 0)
return 0; // no more values
pos--;
} else {
while (stack[pos]->left) {
stack[pos 1] = stack[pos]->left;
pos ;
}
}
*value = stack[pos]->data;
stack[pos] = stack[pos]->right;
*ppos = pos;
return 1;
}
/* compare trees: return 0 if different, 1 if same values, -1 if allocation error */
int isIdentical(const struct Node *root1, const struct Node *root2) {
if (root1 == NULL || root2 == NULL)
return root1 == root2;
size_t depth1 = tree_depth(root1);
size_t depth2 = tree_depth(root2);
const struct Node *stack1[depth1];
const struct Node *stack2[depth2];
size_t pos1 = 0;
size_t pos2 = 0;
stack1[pos1 ] = root1;
stack2[pos2 ] = root2;
for (;;) {
int value1, value2;
int has1 = tree_next(stack1, &pos1, &value1);
int has2 = tree_next(stack2, &pos2, &value2);
if (!has1 && !has2)
return 1;
if (!has1 || !has2 || value1 != value2)
return 0;
}
}