Is a Binary Tree Contained Within Another Binary Tree - C

Question

Hello party people...So I just had an interview that I'm confident I screwed up royally. I had a bunch of questions thrown at me and didn't have enough time to answer the last one.

After getting all beginning questions correct, I was asked to write a function that would determine whether a binary tree b is contained within another binary tree a. I coded the question prior to that correctly, in which he asked me to write a function to determine whether two trees are equal:

int sameTree(struct node *a, struct node *b){
//both empty = TRUE
if(a == NULL && b == NULL)
 return TRUE;
//both not empty, compare them
else if(a != NULL && b != NULL){
 return(
 a->data == b->data &&
 sameTree(a->left, b->left) &&
 sameTree(a->right, b->right)
 );
}
//one empty, one not = FALSE
else 
 return FALSE;

}

Ugh. Just for clearing my conscience, again how would you determine whether tree b is inside tree a?

Thanks for any help guys.

Answer 1

This assumes you want the same tree with the same structure, contains in a:

For one, if b is null and a isn't, a contains b (you should check that in your last else).
Second, these aren't binary search trees (unsorted), so to check if b is inside a you should also traverse a (assuming you rename the function):

int containsTree(struct node *a, struct node *b){
//both empty = TRUE
if(a == NULL && b == NULL)
        return TRUE;
//both not empty, compare them

else if(a != NULL && b != NULL){
    return(
      // sameTree should be changed to allow nulls, as below
      sameTree(a, b)
      // check recursively
      || containsTree(a->left, b)
      || containsTree(a->right, b)
    );
//one empty, one not = FALSE
else 
    return B == NULL;

Answer 2

To check if tree A is contained as-is in tree B, find the node C in B such that C.data == A.data. If there is no such node, A is not contained in B. If C exists, check if A and C are equal using a modified sameTree function - one that ignores mismatches between null children of A and non-null children of C (return true if A.left/right is null).

Thanks @Kobi for the correction.

Answer 3

int in(struct node* outer, struct node* inner){
    if(inner == null){
        return true; // say every tree contains the empty tree
    } else if(outer == null){
        return false;
    } else if(same(outer, inner)){
        return true;
    } else return in(outer->left, inner) || in(outer->right, inner);
}

We must not use the OP's sameTree but rather this function:

int same(struct node* outer, struct node* inner){
    return !inner || outer && outer->data == inner->data && same(outer->left, inner->left) && same(outer->right, inner->right);
}

Or, more verbosely,

int same(struct node* outer, struct node* inner){
    if(inner == null){
        return true;
    } else if(outer == null){
        return false;
    } else if(outer->data == inner->data){
        return same(outer->left, inner->left) && same(outer->right, inner->right);
    } else return false;
}