# CodeStepByStep

## removeMatchingLeaves

Language/Type: C++ binary trees pointers recursion

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`.

`root1` `root2` `root1` after `removeMatchingLeaves(root1, 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;
};
```
Function: Write a C++ function as described, not a complete program.