Leetcode 572. Subtree of Another Tree

Problem Explanation

The problem requires us to check if a tree t is a subtree of another tree s. The inputs are two non-empty binary trees s and t. A binary tree t is a subtree of the binary tree s if t has exactly the same structure and node values with a subtree of s. A subtree is a node and all of its descendants in the tree s. The main tree s could also be considered as a subtree of itself.

To illustrate, let's work through example 1 provided in the problem.

Given tree s:

1
2
3 3
4/ \
54   5
6/ \
71   2

Given tree t:

1
2
34
4/ \
51   2

Tree t is a subtree of s because it has the same structure and node values.

Solution Approach

The solution uses a recursive approach to verify if t is a subtree of s. It starts by checking if s is nullptr. If s is nullptr, it returns false since a non-empty tree t can't be a subtree of an empty tree s.

Then it checks if s and t are the same tree using the function isSameTree(s, t). If they are, it returns true since t is a subtree of s.

If s and t are not the same, it recurses on the left and right subtree of s i.e., isSubtree(s->left, t) and isSubtree(s->right, t). It does this because t could be a subtree in the left or the right subtree of s.

The isSameTree(p, q) function checks if two trees p and q have the same structure and node values. It first checks if either p or q is nullptr. If either is, it returns whether p equals q. If none is nullptr, it checks if the values of the root nodes are equal and recurses on the left and right child nodes to check if they have the same structure and values.

Python Solution

1
2python
3class Solution:
4  def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
5    if not s:
6      return False
7    if self.isSameTree(s, t):
8      return True
9    return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
10
11  def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
12    if not p or not q:
13      return p == q
14    return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Java Solution

1
2java
3public class Solution {
4  public boolean isSubtree(TreeNode s, TreeNode t) {
5    if (s == null)
6      return false;
7    if (isSameTree(s, t))
8      return true;
9    return isSubtree(s.left, t) || isSubtree(s.right, t);
10  }
11
12  private boolean isSameTree(TreeNode p, TreeNode q) {
13    if (p == null || q == null)
14      return p == q;
15    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
16  }
17}

JavaScript Solution

1
2javascript
3class Solution {
4  isSubtree(s, t) {
5    if (s == null)
6      return false;
7    if (this.isSameTree(s, t))
8      return true;
9    return this.isSubtree(s.left, t) || this.isSubtree(s.right, t);
10  }
11
12  isSameTree(p, q) {
13    if (p == null || q == null)
14      return p == q;
15    return p.val == q.val && this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
16  }
17}

C++ Solution

1
2cpp
3class Solution {
4 public:
5  bool isSubtree(TreeNode* s, TreeNode* t) {
6    if (s == nullptr)
7      return false;
8    if (isSameTree(s, t))
9      return true;
10    return isSubtree(s->left, t) || isSubtree(s->right, t);
11  }
12
13 private:
14  bool isSameTree(TreeNode* p, TreeNode* q) {
15    if (!p || !q)
16      return p == q;
17    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
18  }
19};

C# Solution

1
2csharp
3public class Solution {
4  public bool IsSubtree(TreeNode s, TreeNode t) {
5    if (s == null)
6      return false;
7    if (IsSameTree(s, t))
8      return true;
9    return IsSubtree(s.left, t) || IsSubtree(s.right, t);
10  }
11
12  private bool IsSameTree(TreeNode p, TreeNode q) {
13    if (p == null || q == null)
14      return p == q;
15    return p.val == q.val && IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
16  }
17}

Node.js Solution

1
2nodejs
3class Solution {
4  isSubtree(s, t) {
5    if (s == null)
6      return false;
7    if (this.isSameTree(s, t))
8      return true;
9    return this.isSubtree(s.left, t) || this.isSubtree(s.right, t);
10  }
11
12  isSameTree(p, q) {
13    if (p == null || q == null)
14      return p == q;
15    return p.val == q.val && this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
16  }
17}

Kotlin Solution

1
2kotlin
3class Solution {
4    fun isSubtree(s: TreeNode?, t: TreeNode?): Boolean {
5        if (s == null)
6            return false
7        if (isSameTree(s, t))
8            return true
9        return isSubtree(s.left, t) || isSubtree(s.right, t)
10    }
11
12    private fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
13        if (p == null || q == null)
14            return p == q
15        return p.`val` == q.`val` && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
16    }
17}

These solutions in Python, Java, JavaScript, C++, C#, Node.js and Kotlin all have the same approach: they recursively check whether every subtree of the tree 's' is the same as tree 't'. They have a time complexity of O(n*m) where 'n' is the number of nodes in tree 's' and 'm' is the number of nodes in tree 't'. This happens when every subtree of 's' is nearly identical to 't' in structure and values but not completely identical, necessitating a full check of each subtree. Despite this worst-case scenario, these solutions perform well for most inputs.

In conclusion, the problem of checking if a tree is a subtree of another is a common one in the realm of tree-related problems and these solutions demonstrate how recursive techniques can be applied to solve it. Understanding this kind of problem and the approach to solving it not only provides insights in tree traversal but also in recursive algorithm design.