# Solution For Subtree Of Another Tree

The Subtree Of Another Tree problem on LeetCode asks you to determine if a given binary tree is a subtree of another binary tree.

Here is the problem statement:

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.

Example 1:

Given the following tree s:

``````     3
/ \
4   5
/ \
1   2
``````

Given the following tree t:

``````   4
/ \
1   2
``````

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given the following tree s:

``````     3
/ \
4   5
/ \
1   2
/
0
``````

Given the following tree t:

``````   4
/ \
1   2
``````

Return false.

The solution to this problem can be approached using recursion. To check if tree `t` is a subtree of `s`, we need to check if tree `t` is a subtree of both the left and right subtrees of `s`.

We can define a helper function called `isSameTree` that checks if two trees are the same. This function can be called recursively to check if the subtree of `s` at each node is the same as `t`.

Here is the solution in Python:

“`
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s:
return False
if self.isSameTree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

``````def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
if not s and not t:
return True
if not s or not t:
return False
if s.val != t.val:
return False
return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
``````

“`

In the `isSubtree` function, we first check if `s` is empty. If `s` is empty, then `t` cannot be a subtree of `s`.

Next, we check if the root nodes of `s` and `t` are the same using the `isSameTree` function. If they are the same, then `t` is a subtree of `s`.

If the root nodes of `s` and `t` are not the same, then `t` may be a subtree of the left subtree or the right subtree of `s`. We recursively call the `isSubtree` function on the left and right subtrees of `s`.

In the `isSameTree` function, we first check if `s` and `t` are both empty. If they are both empty, then they are the same.

If one of `s` or `t` is empty but the other is not, then they are not the same. If the values of the root nodes of `s` and `t` are different, then they are not the same.

If the values of the root nodes of `s` and `t` are the same, then we recursively check if their left and right subtrees are the same.

This solution has a time complexity of O(m*n) in the worst case, where m and n are the number of nodes in `s` and `t`, respectively. This is because we need to check if `t` is a subtree of each node in `s`. However, in practice, the time complexity is much lower because we can usually prune the search early.

## Step by Step Implementation For Subtree Of Another Tree

```/**
* 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;
*     }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
//check if t is a subtree of s
if(s == null) return false;
if(isSameTree(s,t)) return true;
return isSubtree(s.left,t) || isSubtree(s.right,t);
}

public boolean isSameTree(TreeNode p, TreeNode q) {
//check if p and q are the same tree
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val) return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}```
```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.

Example 1:
Given tree s:

3
/ \
4   5
/ \
1   2
Given tree t:
4
/ \
1   2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

3
/ \
4   5
/ \
1   2
/
0
Given tree t:
4
/ \
1   2
Return false.

def isSubtree(s, t):
# base case:
if not s:
return False
if isSameTree(s, t):
return True
# if the tree with root as current node doesn't match then
# try left and right subtrees one by one
return isSubtree(s.left, t) or isSubtree(s.right, t)

# A tree is subtree of another tree if both with same value
# and subtree structures
def isSameTree(x, y):
# base case
if not x and not y:
return True
# if one of the trees is empty
if not x or not y:
return False
# if value doesn't match
if x.val != y.val:
return False
# if values match recursively check for left and right subtrees
return isSameTree(x.left, y.left) and isSameTree(x.right, y.right)```
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} s
* @param {TreeNode} t
* @return {boolean}
*/
var isSubtree = function(s, t) {
// edge case - if either tree is empty, then
// t can't be a subtree of s
if (!s || !t) {
return false;
}

// if the root values of the two trees are equal,
// then check if the rest of the trees are equal
if (s.val === t.val) {
return isEqual(s, t);
}

// if the root values are not equal, check if t is a
// subtree of s.left or s.right
return isSubtree(s.left, t) || isSubtree(s.right, t);
};

// helper function to check if two trees are equal
var isEqual = function(s, t) {
// if both trees are null, then they are equal
if (!s && !t) {
return true;
}

// if one tree is null and the other isn't, then they are not equal
if (!s || !t) {
return false;
}

// if the root values are not equal, then the trees are not equal
if (s.val !== t.val) {
return false;
}

// check if the left and right subtrees are equal
return isEqual(s.left, t.left) && isEqual(s.right, t.right);
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
// Base case
if (s == nullptr) {
return false;
}
if (t == nullptr) {
return true;
}

// Recursive case
if (isIdentical(s, t)) {
return true;
}
return isSubtree(s->left, t) || isSubtree(s->right, t);
}

bool isIdentical(TreeNode* s, TreeNode* t) {
// Base case
if (s == nullptr && t == nullptr) {
return true;
}
if (s == nullptr || t == nullptr) {
return false;
}

// Recursive case
if (s->val != t->val) {
return false;
}
return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsSubtree(TreeNode s, TreeNode t) {
if(s == null) return false;
if(s.val == t.val && IsSameTree(s,t)) return true;
return IsSubtree(s.left, t) || IsSubtree(s.right, t);
}

public bool IsSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val) return false;
return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]