Subtree of Another Tree

LeetCode 572 | Difficulty: Easy

Easy

Problem 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 = [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]`.

- `-10^4 <= root.val <= 10^4`

- `-10^4 <= subRoot.val <= 10^4`

Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	N/A
Date	2018-05-04

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSubtree(TreeNode s, TreeNode t) {
        if(s!=null)
    return IsSame(s,t) || IsSubtree(s.left,t) || IsSubtree(s.right,t);
    return t==null;
}

private static bool IsSame(TreeNode left, TreeNode right)
{
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    
    return left.val == right.val
                 && IsSame(left.left, right.left)
                 && IsSame(left.right, right.right);
}


}

📜 1 more C# submission(s)

Submission (2018-05-04) — 128 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSubtree(TreeNode s, TreeNode t) {
        if(s!=null)
    return IsSame(s,t) || IsSubtree(s.left,t) || IsSubtree(s.right,t);
    return t==null;
}

private static bool IsSame(TreeNode left, TreeNode right)
{
    if (left != null && right != null)
    {
        return left.val == right.val
                 && IsSame(left.left, right.left)
                 && IsSame(left.right, right.right);

    }
    else if ((left == null && right != null) || (left != null && right == null))
    {
        return false;
    }
    return true;
}


}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Which approach is better here- recursive or iterative?

Hint 2: If recursive approach is better, can you write recursive function with its parameters?

Hint 3: Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?

Hint 4: Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)