Write a method matches that returns a count of the number ofnodes in one tree that match nodes in another tree. A match isdefined as a pair of nodes that are in the same position in the twotrees relative to their overall root and that store the same data.Consider, for example, the following trees:
tree1 +—+ | 3 | +—+ / +—+ +—+ | 4 | | 7 | +—+ +—+ / +—+ +—+ +—+| 0 | | 9 | | 2 |+—+ +—+ +—+ +—+ | 8 | +—+ tree2 +—+ | 3 | +—+ / +—+ +—+ | 6 | | 7 | +—+ +—+ / / +—+ +—+ +—+| 0 | | 9 | | 2 |+—+ +—+ +—+ +—+ | 8 | +—+
The overall root of the two trees match (both are 3). The nodesat 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 theoverall root match (both are 7). The next level of the tree has 2matches for the nodes storing 0 and 2 (there are two nodes thateach store 9 at this level, but they are in different positionsrelative to the overall root of the tree). The nodes at the lowestlevel both store 8, but they aren’t a match because they are indifferent positions. Therefore, these two trees have a total of 4matches. Therefore the calls of tree1.matches(tree2) andtree2.matches(tree1) would each return 4.
Language: Java
Expert Answer
Answer to Write a method matches that returns a count of the number of nodes in one tree that match nodes in another tree. A match…