school project: recursion and binary trees

[hapless90]

ok...

what i need to do is make a recursive function that returns either true or false after seeing if one tree is a subset of another tree.

bool subset_t(specialtree X, specialtree Y)

A is a subset if B like this:

5
/ \
2 7
/ \ / \
1

7
/ \ <=== is a subset of the tree above.

This is what I have so far and my brain is fried. Any help?

bool subset_t(specialtree X, specialtree Y){
if(rootnode(Y) == tree_elt(X){
return (subset_t(node_left(X), node_left(Y)) && subset_t(node_right(X), node_right(Y));
}
else{
subset_t(node_left(X), Y);
subset_t(tree_right(X), Y);
}
}

I know this is not right. But I'm stumped...I've been at this forever.

Thanks!

[jsmith]

Assuming that values in the tree are all unique, then first you have to find B's root value in A. If you don't
find it, then B is not a subset of A. If you find it, then B is a subset of A if and only if the left child tree of
A equals the left child tree of B and the right child tree of A equals the right child tree of B.

From the looks of it, you are close.

- You aren't doing step 1 I gave above.
- You need to deal with leaf nodes (In your example above, 7 is a leaf node, so it has no left or right child).

Also consider that subset_t() returns a bool and only calls itself, which means that at least somewhere in
the function you need to return true and somewhere you have to return false. Currently, you don't do either.

[hamsterman]

first define a function to see if two nodeas are equal

bool equal(node* a, node* b){
    if(a == b) return 1;
    else if(a == 0 || b == 0) return 0;
    return a->value == b->value && equal(a->child1, b->child2) && equal(a->child2, b->child2);
}

then iterate through X and for each node n call equal(n, Y.head) until it returns true