title: Why is inorder and preorder traversal useful for creating an algorithm to decide if T2 is a subtree of T1
body: <p>I'm looking at an interview book and the question is:</p>
  
  <blockquote>
    <p>You have two very large binary trees: <code>T1</code>, with millions of nodes, and
    <code>T2</code>, with hundreds of nodes. Create an algorithm to decide if <code>T2</code> is a
    subtree of <code>T1</code>.</p>
  </blockquote>
  
  <p>The authors mentions this as a possible solution:</p>
  
  <blockquote>
    <p>Note that the problem here specifies that <code>T1</code> has millions of
    nodes—this means that we should be careful of how much space we use.
    Let’s say, for example, <code>T1</code> has 10 million nodes—this means that the
    data alone is about <code>40 mb</code>. <strong>We could create a string representing the
    inorder and preorder traversals</strong>. If <code>T2</code>’s preorder traversal is a
    substring of <code>T1</code>’s preorder traversal, and <code>T2</code>’s inorder traversal is a
    substring of <code>T1</code>’s inorder traversal, then <code>T2</code> is a substring of <code>T1</code>.</p>
  </blockquote>
  
  <p>I'm not quite sure the logic behind as to why if these are true:</p>
  
  <ul>
  <li><code>T2-preorder-traversal-string</code> is a substring of <code>T1-preorder-traversal-string</code></li>
  <li><code>T2-inorder-traversal-string</code> is a substring of <code>T1-inorder-traversal-string</code></li>
  </ul>
  
  <p>That <code>T2</code> must be a substring (although I assume the author means subtree) of <code>T1</code>.  Can I get an explanation to this logic?</p>
  
  <p><strong>EDIT</strong>:  User <em>BartoszMarcinkowski</em> brings up a good point.  Assume both trees have no duplicate nodes.</p>