compare two binary search trees and decide if a subtree is in a binary search tree

Question

I have tried to develop a solution for two problems, the first one is for deciding if two Binary Search Trees (BST) are the same, and the second one is to decide whether a subtree is in BST with all decedent nodes.

This is my solution, and I get some wrong results, and I don't know where the problem is.

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;


int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        compare_bst(root_p->left, root_q->left);
        compare_bst(root_p->right, root_q->right);
    }
    return 1;
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        has_subtree(root->left, sub_root);
        has_subtree(root->right, sub_root);
    }
    return 0;
}

Update

Node* insert(Node* root, int elm) { // -V
    if (!root) {
        root = create_node_bst(elm);
    }
    else if (elm <= root->data) {
        root->left = insert(root->left, elm);
    }
    else {
        root->right = insert(root->right, elm);
    }
    return root;
}

void level_order(Node* root) { // visit all children before grand children [BFS]
    if (!is_empty(root)) {
        Queue *q = malloc(sizeof *q);
        if (q) {
            *q = queue_init;
            enqueue(q, root);
            while (!is_empty_q(q)) {
                Node* cur = front(q);
                printf("%d ", cur->data);
                if (cur->left != NULL)
                    enqueue(q, cur->left);
                if (cur->right != NULL)
                    enqueue(q, cur->right);
                dequeue(q);
            }
        }
        free(q);
    }
}

int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        return compare_bst(root_p->left, root_q->left) && compare_bst(root_p->right, root_q->right);
    }
    return !root_p && !root_q;
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        return has_subtree(root->left, sub_root) || has_subtree(root->right, sub_root);
    }
    return 0;
}

int main() {
    #define MAX 7
    int n = MAX;
    BST bst1 = bst_init;
    BST bst2 = bst_init;
    Node* bst1_root = bst1.root;
    Node* bst2_root = bst2.root;
    int arr[MAX] = {4, 1, 2, 3, 6, 7, 9};
    for (int i = 0; i < n; i++) {
        bst1_root = insert(bst1_root, arr[i]);
       // bst2_root = insert(bst2_root, arr[i]);
        if (i > 4) {
            bst2_root = insert(bst2_root, arr[i]);
        }
       // else
    //         bst2_root = insert(bst2_root, 9);      
    }
        
    
    printf("bst1 and bst2 are the same: %d \n", compare_bst(bst1_root, bst2_root));
    printf("bst1_root has bst2 subtree: %d", has_subtree(bst1_root, bst2_root));
}

I get a wrong result for has_subtree, why is that?

Answer 1

Your code is ignoring the result that comes back from the recursive calls, so those calls are made with no benefit.

In the first function both recursive calls must return 1 for the end result to be 1. In the second function either recursive call must return 1 for that.

Also, when one tree is empty and the other not, then you should not return 1.

Here is a correction:

int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        return compare_bst(root_p->left, root_q->left) &&
               compare_bst(root_p->right, root_q->right);
    }
    return !root_p && !root_q; // Require that both are NULL
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        return has_subtree(root->left, sub_root) ||
               has_subtree(root->right, sub_root);
    }
    return 0;
}

You can shorten this by combining the different conditions into one expression:

int compare_bst(Node* root_p, Node* root_q) {
    return root_p && root_q
         ? root_p->data == root_q->data && 
           compare_bst(root_p->left, root_q->left) &&
           compare_bst(root_p->right, root_q->right)
         : !root_p && !root_q;
}

int has_subtree(Node* root, Node* sub_root) {
    return !!root &&
           (   compare_bst(root, sub_root) ||
               has_subtree(root->left, sub_root) ||
               has_subtree(root->right, sub_root)
           );
}