Practice-It

Write a method 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:

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

public class IntTree {
    private IntTreeNode overallRoot;
    ...
}