Skip to content

572. Subtree of Another Tree 👍

  • Time: $O(mn)$, where $m = |\text{nodes}| \in s$ and $n = |\text{nodes}| \in t$
  • Space: $O(h)$, where $h = \text{height(s)}$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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);
  }
}