title: The most efficient way to test two binary trees for equality
body: <p>How would you implement in Java the binary tree node class and the binary tree class to support the most efficient (from run-time perspective) equal check method (also has to be implemented):</p>
  
  <pre><code>    boolean equal(Node&lt;T&gt; root1, Node&lt;T&gt; root2) {}
  </code></pre>
  
  <p>or</p>
  
  <pre><code>    boolean equal(Tree t1, Tree t2) {}
  </code></pre>
  
  <p>First, I created the Node class as follows:</p>
  
  <pre><code>    public class Node&lt;T&gt; {
          private Node&lt;T&gt; left;
          private Node&lt;T&gt; right;
          private T data;
  
          // standard getters and setters
      }
  </code></pre>
  
  <p>and then the equals method that takes 2 root nodes as an arguments and runs the standard recursive comparison:</p>
  
  <pre><code>    public boolean equals(Node&lt;T&gt; root1, Node&lt;T&gt; root2) {
          boolean rootEqual = false;
          boolean lEqual = false;
          boolean rEqual = false;    
  
          if (root1 != null &amp;&amp; root2 != null) {
              rootEqual = root1.getData().equals(root2.getData());
  
              if (root1.getLeft()!=null &amp;&amp; root2.getLeft() != null) {
                  // compare the left
                  lEqual = equals(root1.getLeft(), root2.getLeft());
              }
              else if (root1.getLeft() == null &amp;&amp; root2.getLeft() == null) {
                  lEqual = true;
              }
              if (root1.getRight() != null &amp;&amp; root2.getRight() != null) {
                  // compare the right
                  rEqual = equals(root1.getRight(), root2.getRight());
              }
              else if (root1.getRight() == null &amp;&amp; root2.getRight() == null) {
                  rEqual = true;
              }
  
              return (rootEqual &amp;&amp; lEqual &amp;&amp; rEqual);
          }
          return false;
      } 
  </code></pre>
  
  <p>My second attempt was to implement the trees using arrays and indexes for traversing. Then the comparison could be done using the bitwise operations (AND) on two arrays - read chunk from 2 arrays and mask one by another using logical AND. I failed to get my code working so I do not post it here (I'd appreciate your implementation of the second idea as well as your improvements). </p>
  
  <p>Any thoughts how to do equality test for binary trees most efficiently?</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>The question assumes structural equality. (Not the semantic equality)</p>
  
  <p>However, code that tests the semantic equality e.g. "Should we consider the two trees to be equal if their contents are identical, even if their structure is not?" Would be just iterating over the tree in-order and it should be straightforward.</p>