CodeStepByStep

Write a function named removeMatchingLeaves that removes any leaf nodes from a binary tree that "match" with a corresponding node in another tree. The function accepts two references to pointers to the roots of two binary trees of integers. For this problem, two nodes "match" if they contain the same data and are located in exactly the same place in the tree relative to the trees' roots. For a node to be removed, it must be a leaf in your tree; but it need not be a leaf in the other tree passed as a parameter. If the second tree doesn't contain a node at that corresponding location or the value there is different, it does not match.

For example, suppose two variables of type BinaryTreeNode called root1 and root2 point to the root nodes of the trees below. The call of removeMatchingLeaves(root1, root2); would modify root1 to store the elements below at right. The leaf nodes containing 0, 2, and 6 have been removed because they match the corresponding nodes in root2. The other leaves from root1, which contain the values 8 and 5, are not removed because they aren't matched in root2.

      3
    /   \
  4       7
 / \     / \
0   9   2   5
   / \
  8   6

       3
     /   \
  28       7
 / \      /
0   9    2
 \   \    \
  8   6    31

      3
    /   \
  4       7
   \       \
    9       5
   /
  8

You should not leak memory; if your function removes nodes from the tree, free the associated memory.

Constraints: You must implement your function recursively and without using loops. Do not construct any new BinaryTreeNode objects in solving this problem (though you may create as many BinaryTreeNode* pointer variables as you like). Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc). You may define helper functions. You should not modify the tree passed in as the parameter. You also should not change the data of any nodes. Your solution must be recursive.

Assume that you are using the BinaryTreeNode structure as defined below:

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