572. Subtree of Another Tree - Explanation

Description

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 = [1,2,3,4,5], subRoot = [2,4,5]

Output: true

Example 2:

Input: root = [1,2,3,4,5,null,null,6], subRoot = [2,4,5]

Output: false

Constraints:

1 <= The number of nodes in both trees <= 100.
-100 <= root.val, subRoot.val <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m + n) space, where n and m are the number of nodes in root and subRoot, respectively.

Hint 1

A subtree of a tree is a tree rooted at a specific node. We need to check whether the given subRoot is identical to any of the subtrees of root. Can you think of a recursive way to check this? Maybe you can leverage the idea of solving a problem where two trees are given, and you need to check whether they are identical in structure and values.

Hint 2

When two trees are identical, it means that every node in both trees has the same value and structure. We can use the Depth First Search (DFS) algorithm to solve the problem. How do you implement this?

Hint 3

We traverse the given root, and at each node, we check if the subtree rooted at that node is identical to the given subRoot. We use a helper function, sameTree(root1, root2), to determine whether the two trees passed to it are identical in both structure and values.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Tree Structure - Understanding node structure with left/right children and how to traverse trees
Depth First Search (DFS) - Used to traverse every node in the main tree and compare subtrees recursively
Tree Comparison - Checking if two trees are structurally identical with matching values at each node

1. Depth First Search (DFS)

Intuition

To check whether one tree is a subtree of another, we do two things:

Walk through every node of the main tree (root) using DFS.
At each node, check if the subtree starting here is exactly the same as subRoot.

So for every node in the big tree:

If its value matches subRoot's root, we compare both subtrees fully.
If they are identical, subRoot is a subtree.
Otherwise, continue searching on the left and right children.

The helper sameTree simply checks whether two trees match exactly, node-for-node.

Algorithm

If subRoot is empty → return true (empty tree is always a subtree).
If root is empty but subRoot is not → return false.
At the current root node:
- If sameTree(root, subRoot) is true, return true.
Recursively check:
- isSubtree(root.left, subRoot)
- isSubtree(root.right, subRoot)
Return true if either side returns true.

sameTree(root1, root2):

If both nodes are null → return true.
If only one is null → return false.
If values differ → return false.
Recursively check left children and right children.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False

        if self.sameTree(root, subRoot):
            return True
        return (self.isSubtree(root.left, subRoot) or
               self.isSubtree(root.right, subRoot))

    def sameTree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root and not subRoot:
            return True
        if root and subRoot and root.val == subRoot.val:
            return (self.sameTree(root.left, subRoot.left) and
                   self.sameTree(root.right, subRoot.right))
        return False

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        }
        if (root == null) {
            return false;
        }

        if (sameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) ||
               isSubtree(root.right, subRoot);
    }

    public boolean sameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root != null && subRoot != null && root.val == subRoot.val) {
            return sameTree(root.left, subRoot.left) &&
                   sameTree(root.right, subRoot.right);
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!subRoot) {
            return true;
        }
        if (!root) {
            return false;
        }

        if (sameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root->left, subRoot) ||
               isSubtree(root->right, subRoot);
    }

    bool sameTree(TreeNode* root, TreeNode* subRoot) {
        if (!root && !subRoot) {
            return true;
        }
        if (root && subRoot && root->val == subRoot->val) {
            return sameTree(root->left, subRoot->left) &&
                   sameTree(root->right, subRoot->right);
        }
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @param {TreeNode} subRoot
     * @return {boolean}
     */
    isSubtree(root, subRoot) {
        if (!subRoot) {
            return true;
        }
        if (!root) {
            return false;
        }

        if (this.sameTree(root, subRoot)) {
            return true;
        }
        return (
            this.isSubtree(root.left, subRoot) ||
            this.isSubtree(root.right, subRoot)
        );
    }

    /**
     * @param {TreeNode} root
     * @param {TreeNode} subRoot
     * @return {boolean}
     */
    sameTree(root, subRoot) {
        if (!root && !subRoot) {
            return true;
        }
        if (root && subRoot && root.val === subRoot.val) {
            return (
                this.sameTree(root.left, subRoot.left) &&
                this.sameTree(root.right, subRoot.right)
            );
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {

    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        }
        if (root == null) {
            return false;
        }

        if (SameTree(root, subRoot)) {
            return true;
        }
        return IsSubtree(root.left, subRoot) ||
               IsSubtree(root.right, subRoot);
    }

    public bool SameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root != null && subRoot != null && root.val == subRoot.val) {
            return SameTree(root.left, subRoot.left) &&
                   SameTree(root.right, subRoot.right);
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if subRoot == nil {
        return true
    }
    if root == nil {
        return false
    }

    if sameTree(root, subRoot) {
        return true
    }
    return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func sameTree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil && subRoot == nil {
        return true
    }
    if root != nil && subRoot != nil && root.Val == subRoot.Val {
        return sameTree(root.Left, subRoot.Left) && sameTree(root.Right, subRoot.Right)
    }
    return false
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        if (subRoot == null) {
            return true
        }
        if (root == null) {
            return false
        }

        if (sameTree(root, subRoot)) {
            return true
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
    }

    fun sameTree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        if (root == null && subRoot == null) {
            return true
        }
        if (root != null && subRoot != null && root.`val` == subRoot.`val`) {
            return sameTree(root.left, subRoot.left) && sameTree(root.right, subRoot.right)
        }
        return false
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        if subRoot == nil {
            return true
        }
        if root == nil {
            return false
        }
        if sameTree(root, subRoot) {
            return true
        }
        return isSubtree(root?.left, subRoot) || isSubtree(root?.right, subRoot)
    }

    func sameTree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        if root == nil && subRoot == nil {
            return true
        }
        if let root = root, let subRoot = subRoot, root.val == subRoot.val {
            return sameTree(root.left, subRoot.left) && sameTree(root.right, subRoot.right)
        }
        return false
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m + n)$

Where $m$ is the number of nodes in $subRoot$ and $n$ is the number of nodes in $root$ .

2. Serialization And Pattern Matching

Intuition

Instead of comparing trees directly, we can first turn each tree into a string and then just check whether one string is contained in the other.

Serialize both root and subRoot into strings using the same traversal (for example, preorder).
While serializing, we must include markers for null children (like #) and separators (like $) so different shapes don't accidentally look the same in the string.
Once we have:
- S_root = serialization of the main tree
- S_sub = serialization of the subtree
  the problem becomes:
  "Is S_sub a substring of S_root?"

To efficiently check this, we can use a linear-time pattern matching algorithm (like Z-function or KMP) instead of naive substring search.

Algorithm

Serialize a tree
- Use preorder traversal.
- For each node:
  - Append a separator (e.g., $) + node value.
- For each null child, append a special marker (e.g., #$ or just #).
- This ensures structure and values are uniquely encoded.
Build strings
- Let S_sub = serialization of subRoot.
- Let S_root = serialization of root.
Combine for pattern matching
- Build a combined string:
  combined = S_sub + "|" + S_root
  (| is just a separator that does not appear in the serializations.)
Run pattern matching
- Compute the Z-array (or use another pattern-matching algorithm) on combined.
- Let m = length(S_sub).
- Scan the Z-values:
  - If any Z[i] == m, then S_sub appears completely starting at that position → subRoot is a subtree → return true.
If no such position is found, return false.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if root == None:
            return "$#"

        return ("$" + str(root.val) + self.serialize(root.left) + self.serialize(root.right))

    def z_function(self, s: str) -> list:
        z = [0] * len(s)
        l, r, n = 0, 0, len(s)
        for i in range(1, n):
            if i <= r:
                z[i] = min(r - i + 1, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l, r = i, i + z[i] - 1
        return z

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        serialized_root = self.serialize(root)
        serialized_subRoot = self.serialize(subRoot)
        combined = serialized_subRoot + "|" + serialized_root

        z_values = self.z_function(combined)
        sub_len = len(serialized_subRoot)

        for i in range(sub_len + 1, len(combined)):
            if z_values[i] == sub_len:
                return True
        return False

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "$#";
        }
        return "$" + root.val + serialize(root.left) + serialize(root.right);
    }

    public int[] z_function(String s) {
        int[] z = new int[s.length()];
        int l = 0, r = 0, n = s.length();
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String serialized_root = serialize(root);
        String serialized_subRoot = serialize(subRoot);
        String combined = serialized_subRoot + "|" + serialized_root;

        int[] z_values = z_function(combined);
        int sub_len = serialized_subRoot.length();

        for (int i = sub_len + 1; i < combined.length(); i++) {
            if (z_values[i] == sub_len) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "$#";
        }
        return "$" + to_string(root->val) +
                serialize(root->left) + serialize(root->right);
    }

    vector<int> z_function(string s) {
        vector<int> z(s.length());
        int l = 0, r = 0, n = s.length();
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string serialized_root = serialize(root);
        string serialized_subRoot = serialize(subRoot);
        string combined = serialized_subRoot + "|" + serialized_root;

        vector<int> z_values = z_function(combined);
        int sub_len = serialized_subRoot.length();

        for (int i = sub_len + 1; i < combined.length(); i++) {
            if (z_values[i] == sub_len) {
                return true;
            }
        }
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {string}
     */
    serialize(root) {
        if (root === null) {
            return '$#';
        }
        return (
            '$' +
            root.val +
            this.serialize(root.left) +
            this.serialize(root.right)
        );
    }

    /**
     * @param {string} s
     * @return {number[]}
     */
    z_function(s) {
        const z = new Array(s.length).fill(0);
        let l = 0,
            r = 0,
            n = s.length;
        for (let i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    /**
     * @param {TreeNode} root
     * @param {TreeNode} subRoot
     * @return {boolean}
     */
    isSubtree(root, subRoot) {
        const serialized_root = this.serialize(root);
        const serialized_subRoot = this.serialize(subRoot);
        const combined = serialized_subRoot + '|' + serialized_root;

        const z_values = this.z_function(combined);
        const sub_len = serialized_subRoot.length;

        for (let i = sub_len + 1; i < combined.length; i++) {
            if (z_values[i] === sub_len) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public string Serialize(TreeNode root) {
        if (root == null) {
            return "$#";
        }
        return "$" + root.val +
                Serialize(root.left) + Serialize(root.right);
    }

    public int[] ZFunction(string s) {
        int[] z = new int[s.Length];
        int l = 0, r = 0, n = s.Length;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.Min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        string serialized_root = Serialize(root);
        string serialized_subRoot = Serialize(subRoot);
        string combined = serialized_subRoot + "|" + serialized_root;

        int[] z_values = ZFunction(combined);
        int sub_len = serialized_subRoot.Length;

        for (int i = sub_len + 1; i < combined.Length; i++) {
            if (z_values[i] == sub_len) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func serialize(root *TreeNode) string {
    if root == nil {
        return "$#"
    }
    return "$" + strconv.Itoa(root.Val) + serialize(root.Left) + serialize(root.Right)
}

func zFunction(s string) []int {
    n := len(s)
    z := make([]int, n)
    l, r := 0, 0

    for i := 1; i < n; i++ {
        if i <= r {
            z[i] = min(r-i+1, z[i-l])
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            z[i]++
        }
        if i+z[i]-1 > r {
            l = i
            r = i + z[i] - 1
        }
    }
    return z
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    serializedRoot := serialize(root)
    serializedSubRoot := serialize(subRoot)
    combined := serializedSubRoot + "|" + serializedRoot

    zValues := zFunction(combined)
    subLen := len(serializedSubRoot)

    for i := subLen + 1; i < len(combined); i++ {
        if zValues[i] == subLen {
            return true
        }
    }
    return false
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private fun serialize(root: TreeNode?): String {
        return when (root) {
            null -> "$#"
            else -> "$${root.`val`}${serialize(root.left)}${serialize(root.right)}"
        }
    }

    private fun zFunction(s: String): IntArray {
        val n = s.length
        val z = IntArray(n)
        var l = 0
        var r = 0

        for (i in 1 until n) {
            if (i <= r) {
                z[i] = minOf(r - i + 1, z[i - l])
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++
            }
            if (i + z[i] - 1 > r) {
                l = i
                r = i + z[i] - 1
            }
        }
        return z
    }

    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        val serializedRoot = serialize(root)
        val serializedSubRoot = serialize(subRoot)
        val combined = serializedSubRoot + "|" + serializedRoot

        val zValues = zFunction(combined)
        val subLen = serializedSubRoot.length

        return (subLen + 1 until combined.length).any { i -> zValues[i] == subLen }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func serialize(_ root: TreeNode?) -> String {
        guard let root = root else {
            return "$#"
        }
        return "$\(root.val)" + serialize(root.left) + serialize(root.right)
    }

    func zFunction(_ s: String) -> [Int] {
        let n = s.count
        var z = [Int](repeating: 0, count: n)
        var l = 0, r = 0
        let chars = Array(s)

        for i in 1..<n {
            if i <= r {
                z[i] = min(r - i + 1, z[i - l])
            }
            while i + z[i] < n && chars[z[i]] == chars[i + z[i]] {
                z[i] += 1
            }
            if i + z[i] - 1 > r {
                l = i
                r = i + z[i] - 1
            }
        }
        return z
    }

    func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        let serializedRoot = serialize(root)
        let serializedSubRoot = serialize(subRoot)
        let combined = serializedSubRoot + "|" + serializedRoot

        let zValues = zFunction(combined)
        let subLen = serializedSubRoot.count

        for i in (subLen + 1)..<combined.count {
            if zValues[i] == subLen {
                return true
            }
        }
        return false
    }
}

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m + n)$

Where $m$ is the number of nodes in $subRoot$ and $n$ is the number of nodes in $root$ .

Common Pitfalls

Confusing Subtree with Substructure

A subtree must match exactly from a node down to all its leaves. A common mistake is checking only if the values match without verifying that the entire structure below also matches. If subRoot has children, those children must also exist and match in the main tree. Simply finding a node with the same value is not sufficient.

Incorrect Null Handling in Tree Comparison

When comparing two trees for equality, both trees must have null children in the same positions. A frequent error is returning true when one node is null and the other is not, or failing to check both left and right subtrees. The base case must ensure that both nodes being compared are either both null (return true) or both non-null with matching values before recursing.