Course4all
Join us on telegram
Home/dsa/Trees/Subtree of Another Tree

Subtree of Another Tree

Master this topic with zero to advance depth.

Subtree of Another Tree

Check if a tree subRoot is a subtree of root.

Easy

Examples

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

Level I: Recursive DFS (Is Match?)

Intuition

A tree s is a subtree of t if:

  1. s and t are identical.
  2. s is a subtree of t.left.
  3. s is a subtree of t.right.
⏱ O(M * N) (where M, N are nodes in each tree)💾 O(H)

Detailed Dry Run

root(3) != sub(4). check root(4) == sub(4) -> YES (IsSameTree).

java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSame(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null || s.val != t.val) return false;
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}
Approach 2

Level II: Preorder String Matching (O(N))

Intuition

Serialize both trees into strings using preorder traversal. Add special markers for null nodes (e.g., '#') and separate values to avoid ambiguity (e.g., ','). If the serialized subRoot is a substring of serialized root, it's a subtree.

Diagram

Tree: 3(4,5) -> Preorder: ",3,4,#,#,5,#,#" Subtree: 4 -> Preorder: ",4,#,#" Match found in ",3,4,#,#,5,#,#"!
⏱ O(N + M)💾 O(N + M)

Detailed Dry Run

Serialize root: ^3,4,1,#,#,2,#,#,5,#,#. Serialize sub: ^4,1,#,#,2,#,#. Sub exists in Root -> True.

java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String r = serialize(root);
        String s = serialize(subRoot);
        return r.contains(s);
    }
    private String serialize(TreeNode node) {
        if (node == null) return ",#";
        return "," + node.val + serialize(node.left) + serialize(node.right);
    }
}
← Previous QuestionSymmetric Tree
Next Question →Diameter of Binary Tree