> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/501-600/subtree-of-another-tree.md).

# 572. Subtree of Another Tree

### Description

Given two **non-empty** binary trees **s** and **t**, check whether tree **t** has exactly the same structure and node values with a subtree of **s**. A subtree of **s** is a tree consists of a node in **s** and all of this node's descendants. The tree **s** could also be considered as a subtree of itself.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/subtree-of-another-tree/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

s = \[3, 4, 5, 1, 2]

<div align="left"><img src="/files/-MUHTvRK88Rtxmg93Xs0" alt=""></div>

t = \[4, 1, 2]

<div align="left"><img src="/files/-MUHU7Ntuf70Hy2n8RyY" alt=""></div>

**Output:** true
{% endtab %}

{% tab title="Example 2" %}
**Input:**

s = \[3, 4, 5, 1, 2, null, null, null, null, 0]

<div align="left"><img src="/files/-MUHUpfTvRgaXWnkXeQN" alt=""></div>

t = \[4, 1, 2]

<div align="left"><img src="/files/-MUHU7Ntuf70Hy2n8RyY" alt=""></div>

**Output:** false
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```java
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { 
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(m^2 + n^2 + m*n). A total of n nodes of the tree s and m 
 *    nodes of tree t are traversed. Assuming string concatenation takes O(k) 
 *    time for strings of length k and indexOf takes O(m*n).
 * Space complexity : O(max(m,n)). The depth of the recursion tree can go 
 *    upto n for tree t and m for tree s in worst case.
 */

public class Solution {
    HashSet < String > trees = new HashSet < > ();
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree1 = preorder(s, true);
        String tree2 = preorder(t, true);
        return tree1.indexOf(tree2) >= 0;
    }
    public String preorder(TreeNode t, boolean left) {
        if (t == null) {
            if (left)
                return "lnull";
            else
                return "rnull";
        }
        return "#"+ t.val + " " + preorder(t.left, true) + " " + 
                preorder(t.right, false);
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(m*n). In worst case(skewed tree) traverse function 
 *    takes O(m*n) time.
 * Space complexity : O(n). The depth of the recursion tree can go upto n. 
 *    n refers to the number of nodes in s.
 */
 
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) {
            return false;
        }
        return isSameTree(s, t) || isSubtree(s.left, t) || 
                isSubtree(s.right, t);
    }
    
    private boolean isSameTree(TreeNode n1, TreeNode n2) {
        if(n1 == null && n2 == null) {
            return true;
        }
        if(n1 == null || n2 == null) {
            return false;
        }
        return n1.val == n2.val && isSameTree(n1.left, n2.left) && 
                isSameTree(n1.right, n2.right);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*