50143. AND & OR of Trees

I'm a slow walker, but I never walk backwards.

Task Description

We will AND and OR two trees to generate a new tree.

The AND operation is similar to intersection of two sets. If we AND two trees $A$ and $B$ then only the nodes that appear in both $A$ and $B$ will appear in the result tree $C$. The value of a new tree node will be the product of the values from the two corresponding tree nodes from the two trees. An example of ANDing two trees is shown in the following figure.

Similarly we can define the OR operation, which is like the union of two sets. If we OR two trees $A$ and $B$ then a node will appear in the result tress $C$ if the node appears in $A$ or in $B$. The value of the new tree node will be the sum of the values of the two corresponding tree nodes in $A$ and $B$. If a node only appears in $A$ (or in $B$), the the new value will be the value of $A$ (or $B$). An example of OR operation is shown in the following figure.
Write two functions to do tree AND and OR. The input of the function is the pointers to the roots of trees $A$ and $B$, and the function will construct the result tree $C$ and return the root of $C$. You can use malloc() to create new nodes in the function if necessary. The tree node structure and function prototype is defined in the following header file "tree.h".

typedef struct Node{
    int val;
    struct Node *left, *right;
} Node;
 
Node *treeAND(Node *root1, Node *root2);
Node *treeOR(Node *root1, Node *root2);

You can use the following main.c to check your functions.

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
 
void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}
 
void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}
 
Node *insertBST(Node *root, int val) {
    if (root == NULL) {
        root = (Node *) malloc(sizeof(Node));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    if (val < root->val)
        root->left = insertBST(root->left, val);
    else
        root->right = insertBST(root->right, val);
    return root;
}
 
int main() {
    int op, n1, n2, val;
    scanf("%d%d%d", &op, &n1, &n2);
    Node *tree1 = NULL;
    Node *tree2 = NULL;
    for (int i = 0; i < n1; ++i) {
        scanf("%d", &val);
        tree1 = insertBST(tree1, val);
    }
    for (int i = 0; i < n2; ++i) {
        scanf("%d", &val);
        tree2 = insertBST(tree2, val);
    }
 
    Node *tree = (op) ? treeAND(tree1, tree2) : treeOR(tree1, tree2);
 
    preorder(tree);
    printf("\n");
    inorder(tree);
    printf("\n");
 
    return 0;
}

Input Format of main.c

The input has four lines. The first line is the type of the operation -- $1$ for AND, and $0$ for OR. The second line has two integers $n1$ and $n2$, which are the number of nodes in trees $A$ and $B$. The third line and forth line are the values of the tree nodes in $A$ and $B$. They will be inserted into a binary search tree in the order they appear in the input.

  • $1 \lt n1, n2 \lt 100$
  • $0 \lt \text{node values} \lt 101$

Output Format of main.c

The first line is the result of a preorder traversal of the new tree $C$. The second line is the retuls of an inorder traversal of the new tree $C$.

Subtasks

  • 50 points: AND opertion
  • 50 points: OR opertion

Sample Input 1

1
8 8
4 1 7 3 2 5 6 8
6 2 1 5 3 4 7 8

Sample Output 1

24 2 15 6 49 64
2 6 15 24 49 64

Sample Input 2

0
8 8
4 1 7 3 2 5 6 8
6 2 1 5 3 4 7 8

Sample Output 2

10 3 1 8 5 4 14 5 6 16
1 3 5 4 8 10 5 6 14 16

Discussion