Question

Write a recursive function that compares two given binary trees. It returns 1 if the two trees are different, and it returns 0 otherwise. The function signature is: int treeDiff (node "a, node *b); Write a recursive function that counts how many nodes in a tree have a single child. The function signature is: int countoneChild(node "root);

Answer 1

struct node {
    node *left;
    node *right;
    int data;
};

int treeDiff(node *a, node *b) {
    if (a == NULL && b == NULL) {
        return 0;
    } else if (a == NULL || b == NULL) {
        return 1;
    } else {
        if (a->data == b->data && treeDiff(a->left, b->left) == 0 && treeDiff(a->right, b->right) == 0) {
            return 0;
        } else {
            return 1;
        }
    }
}

int countOneChild(node *root) {
    if (root == NULL) {
        return 0;
    } else {
        int count = 0;
        if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
            count = 1;
        }
        return count + countOneChild(root->left) + countOneChild(root->right);
    }
}