title: Comparing tree structures of haystack and needle
body: <p>I want to write a method that would record all positions of nodes of haystack starting from where the pattern (structure) of itself matches as that of the needle. The value stored in the node doesn't need to be equal, its just the pattern that is supposed to match.</p>
  
  <p><strong>Illustration</strong> </p>
  
  <p><strong>Example 1</strong></p>
  
  <p>If I have the following haystack and needle</p>
  
  <p><img src="https://i.stack.imgur.com/1VgAe.png" alt="enter image description here"></p>
  
  <p>In the example above, the program is expected to record</p>
  
  <pre><code>ROOT
  ROOT-&gt;Left
  </code></pre>
  
  <p><strong>Example 2</strong></p>
  
  <p>If I have the same haystack as that of above and my needle as </p>
  
  <p><img src="https://i.stack.imgur.com/0RKhe.png" alt="enter image description here"></p>
  
  <p>Then my program is expected to record,</p>
  
  <pre><code>ROOT
  ROOT-&gt;Left
  ROOT-&gt;Right
  </code></pre>
  
  <p>However, it seems like the way I am implementing my code is flawed because my method even records positions that shouldn't have been true.</p>
  
  <p>The way I am implementing my code is, I have the following method that would return a list which contains all such positions and I am using a isSubtree method to check if the pattern starting from a particular node finds a match.</p>
  
  <pre><code>public static List&lt;String&gt; searchForNeedleInHaystack(Node haystack,
          Node needle) {
      List&lt;String&gt; resultList = new ArrayList&lt;String&gt;();
      if(haystack.getLeftChild() != null) {
          value = value + "L";//value is just a global string variable initially ""
          if(isSubtree(haystack.getLeftChild(), needle)) {
              resultList.add(value);
          } else {
              if(value.length() &gt; 1)
                  value = value.substring(0, value.length() - 1);
          }
          searchForNeedleInHaystack(haystack.getLeftChild(), needle);
      }
  
      if(haystack.getRightChild() != null) {
          value = value + "R";
          if(isSubtree(haystack.getRightChild(), needle)) {
              resultList.add(value);
          } else {
              if(value.length() &gt; 1)
                  value = value.substring(0, value.length() - 1);
          }
          searchForNeedleInHaystack(haystack.getRightChild(), needle);
      }
      return resultList;
  }
  
  public static boolean isSubtree(Node haystack, Node needle) {
      if(needle == null)
          return true;
      if(haystack == null)
          return false;
      return isSubtree(haystack.getLeftChild(), needle.getLeftChild()) &amp;&amp; isSubtree(haystack.getRightChild(), needle.getRightChild());
  }
  </code></pre>
  
  <p><strong>Node class</strong></p>
  
  <pre><code>public class Node {
      private String info;
      private Node leftChild = null;
      private Node rightChild = null;
  
      public Node() {
          this("");
      }
  
      public Node(String info) {
          this.info = info;
      }
  
      public void setinfo(String info) {
          this.info = info;
      }
  
      public void setLeftChild(Node n) {
          leftChild = n;
      }
  
      public void setRightChild(Node n) {
          rightChild = n;
      }
  
      public Node getLeftChild() {
          return leftChild;
      }
  
      public Node getRightChild() {
          return rightChild;
      }
  
      public String getinfo() {
          return info;
      }
  
      public boolean isLeaf() {
          return rightChild == null &amp;&amp; leftChild == null;
      }   
  }
  </code></pre>
  
  <p><strong>Problem</strong></p>
  
  <p>I just wanted to know what logic could I perhaps use so that I can compare for subtree structures successfully?</p>
  
  <p>Thanks in advance!</p>