Write a method called matches that returns a count of the number of nodes in one tree that match nodes in another tree. A match is defined as a pair of nodes that are in the same position in the two trees relative to their overall root and that store the same data. Consider, for example, the following trees:

The overall root of the two trees match (both are 3). The nodes at the top of the left subtrees of the overall root do not match (one is 4 and one is 6). The top of the right subtrees of the overall root match (both are 7). The next level of the tree has 2 matches for the nodes storing 0 and 2 (there are two nodes that each store 9 at this level, but they are in different positions relative to the overall root of the tree). The nodes at the lowest level both store 8, but they aren’t a match because they are in different positions. Therefore, these two trees have a total of 4 matches. Therefore the calls of tree1.matches(tree2) and tree2.matches(tree1) would each return 4 .

Transcribed Image Text:

tree 1 tree 2 3 3 4 6. 2 6. 8 8