572. Subtree of Another Tree LeetCode Solution

In this guide, you will get 572. Subtree of Another Tree LeetCode Solution with the best time and space complexity. The solution to Subtree of Another Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Subtree of Another Tree solution in C++
Subtree of Another Tree solution in Java
Subtree of Another Tree solution in Python
Additional Resources

572. Subtree of Another Tree LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(mn), where m = |\text{nodes}| \in s and n = |\text{nodes}| \in t
Space Complexity: O(h), where h = \text{height(s)}

572. Subtree of Another Tree LeetCode Solution in C++

class Solution {
 public:
  bool isSubtree(TreeNode* s, TreeNode* t) {
    if (s == nullptr)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
  }

 private:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q)
      return p == q;
    return p->val == q->val &&              //
           isSameTree(p->left, q->left) &&  //
           isSameTree(p->right, q->right);
  }
};
/* code provided by PROGIEZ */

572. Subtree of Another Tree LeetCode Solution in Java

class Solution {
  public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
  }

  private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null)
      return p == q;
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }
}
// code provided by PROGIEZ