[4.7] T2 is a subtree of T1

1. Example



10 million nodes = 10*10^6 = 10 ^7
int 32 bit = 4 byte
4B * 10^7 = 40 MB



2. Implementation

// Approach #1  Memory is not an issue

T1 String traversal = a string s1 O(10^6)
T2 String traversal = a string s2 O(100)
s2 is a substring of s1 if preorder traversal and inorder traversal both apply

substring : check using a suffix tree
suffix tree of 10^6 length string ==> char 2 byte [26]
2B*26*10^6 = 52MB

26*26*26......
suffix tree is memory intensive

A1: b i  b s

s
ibs
b s
    ibs
                         root
            /              |         \
           B   0,2     I   1      S 3
         /    \           |       
       I0      S2     B  1
       |                   |
       B0               S 1
       |
       S0

// Approach #2 Memory is an issue and we try this approach
// Worst case :Time O(n*m), where n and m is the sizes of trees T1 and T2, respectively
// Avg Case   :Time O(k*m + n)
// If k is the occcurrences of T2'root in T1, the worst case runtime can be characterized as O(k*m + n)

boolean containsTree(TreeNode t1, TreeNode t2)
{


      // validate the input
      if  ( t2 == null )
          return true;



      
      return subTree( t1, t2);




}
// Find the root with the same value
boolean sunTree(TreeNode r1, TreeNode r2)
{ 



      // Base case
      if ( r1 == null) // till the leaf and cannot find the subtree
         return false;
      

      
      if (r1.val === r2.val)
      {
          if (  matchTree(r1, r2)  )
             return true;    
      }



      return subTree(r1.left, r2) || subTree(r1.right, r2);
 

}

boolean matchTree(TreeNode r1, TreeNode r2)
{
      

      if (r1 == null && r2 == null)
          return true;
      if ( r1 == null || r2 == null )
          reutrn false;
      if (r1.val != r2.val)
          return false;

    
      return matchTree( r1.left, r2.left ) && matchTree(r1.right, r2.right);
    
}

3. Similar ones