Algorithm

Problem Name: 572. Subtree of Another Tree

Problem Link: https://leetcode.com/problems/subtree-of-another-tree/

Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of `root` with the same structure and node values of` subRoot` and `false` otherwise.

A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node's descendants. The tree `tree` could also be considered as a subtree of itself.

Example 1:

```Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
```

Example 2:

```Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
```

Constraints:

• The number of nodes in the `root` tree is in the range `[1, 2000]`.
• The number of nodes in the `subRoot` tree is in the range `[1, 1000]`.
• `-104 <= root.val <= 104`
• `-104 <= subRoot.val <= 104`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
bool equal(struct TreeNode *node, struct TreeNode *t) {
if (!node && !t) return true;
if (!node || !t || node->val != t->val) return false;
return equal(node->left, t->left) && equal(node->right, t->right);
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if (equal(s, t) ||
(s && isSubtree(s->left, t)) ||
(s && isSubtree(s->right, t))) return true;
return false;
}
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2], subRoot = [4,1,2]

Output

cmd
true

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s) return !t;
return isEqual(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}

bool isEqual(TreeNode* p, TreeNode* t){
if(!p || !t) return !p && !t;
return p->val == t->val && isEqual(p->left, t->left) && isEqual(p->right, t->right);
}
};
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2], subRoot = [4,1,2]

Output

cmd
true

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (isSubtreeHelper(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSubtreeHelper(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
if (root.val != subRoot.val) {
return false;
}
return isSubtreeHelper(root.left, subRoot.left) && isSubtreeHelper(root.right, subRoot.right);
}
}
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

Output

cmd
false

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const isSubtree = function(s, t) {
if (s == null) return false
if (isSame(s, t)) return true
return isSubtree(s.left, t) || isSubtree(s.right, t)
};

function isSame(s, t) {
if (s == null && t == null) return true
if (s == null || t == null) return false
if (s.val !== t.val) return false
return isSame(s.left, t.left) && isSame(s.right, t.right)
}
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

Output

cmd
false

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def traverse(node):
if not node: return "^"
return "\$"+str(node.val)+"?"+traverse(node.left)+"@"+traverse(node.right)
return traverse(t) in traverse(s)
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2], subRoot = [4,1,2]

Output

cmd
true

#6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0572_SubtreeOfAnotherTree
{
public bool IsSubtree(TreeNode s, TreeNode t)
{
return Traverse(s, t);
}

private bool Traverse(TreeNode s, TreeNode t)
{
return s != null && (EqualTree(s, t) || Traverse(s.left, t) || Traverse(s.right, t));
}

private bool EqualTree(TreeNode s, TreeNode t)
{
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && EqualTree(s.left, t.left) && EqualTree(s.right, t.right);
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,4,5,1,2], subRoot = [4,1,2]

Output

cmd
true
Advertisements