Log inSign up
easyleetcodeNot Started

Subtree of Another Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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 · Example 1: Valid Subtree:

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2] Tree: 3 subRoot: / \ 4 4 5 / \ / \ 1 2 1 2
Output: true
Explanation: Subtree rooted at node 4 matches subRoot exactly.

Example 2 · Example 2: Extra Child Mismatch:

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2] Tree: 3 subRoot: / \ 4 4 5 / \ / \ 1 2 1 2 / 0
Output: false
Explanation: Node 2 has child 0 in root, but subRoot has no child 0. Not a subtree.

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine tree traversal with identical tree verification.
  • Understand why a subtree requires identical leaf terminations.
  • Recognize string serialization as an alternative O(n + m) approach.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Check if one binary tree is a subtree of another.
  • Complete structural and value match.
  • Tree pattern matching.

Algorithmic Decision Tree:

  • If root == null return false.
  • If isSame(root, subRoot) return true.
  • return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).

Connected Patterns:

Same TreeSymmetric TreeFind Duplicate Subtrees

1. Recursive Tree Equality Check

Intuition

Define isSame(a, b). In isSubtree(root, subRoot), if isSame(root, subRoot) is true return true; otherwise recurse on left and right.

When to apply: Standard intuitive solution.

Algorithm

  1. Step 1: If root == null return false.
  2. Step 2: If isSame(root, subRoot) return true.
  3. Step 3: Return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 bool isSame(TreeNode* a, TreeNode* b) {
9 if (!a && !b) return true;
10 if (!a || !b) return false;
11 return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);
12 }
13public:
14 bool isSubtree(TreeNode* root, TreeNode* subRoot) {
15 if (!root) return false;
16 if (isSame(root, subRoot)) return true;
17 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
18 }
19};
20
21int main() {
22 // Sample driver execution
23 cout << "Execution completed successfully." << endl;
24 return 0;
25}
26

Time & Space Complexity

  • Time complexity: O(n * m) — Worst-case checks all m nodes of subRoot at each of the n nodes of root.
  • Space complexity: O(h) — Call stack depth bounded by tree height h.

2. Tree Hash / Merkle Tree Hashing

Intuition

Compute a hash for each subtree. If a subtree's hash matches subRoot's hash, run isSameTree as verification to avoid hash collisions.

When to apply: When speeding up equality checks with hash fingerprints.

Algorithm

  1. Step 1: Compute hash(node) = (node.val * P + hash(left) * P2 + hash(right) * P3) % MOD.
  2. Step 2: If hash matches subRoot's hash, verify with isSameTree.
  3. Step 3: Return true if verified match found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 bool isSame(TreeNode* a, TreeNode* b) {
9 if (!a && !b) return true;
10 if (!a || !b) return false;
11 return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);
12 }
13public:
14 bool isSubtree(TreeNode* root, TreeNode* subRoot) {
15 if (!root) return false;
16 if (root->val == subRoot->val && isSame(root, subRoot)) return true;
17 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
18 }
19};
20
21int main() {
22 // Sample driver execution
23 cout << "Execution completed successfully." << endl;
24 return 0;
25}
26

Time & Space Complexity

  • Time complexity: O(n + m) — Hash computation takes O(n + m); verification takes O(m) on rare hash collisions.
  • Space complexity: O(h) — Recursion stack takes O(h).

3. Serialization with Preorder String Matching

Intuition

Serialize both trees with unique delimiters: ,# for null and , before values (e.g. ,4,#,#). Then check if s2 is a substring of s1. Delimiters prevent false matches like 12 matching 2.

When to apply: Optimal linear time solution.

Algorithm

  1. Step 1: Serialize tree: serialize(node) = , + node.val + serialize(left) + serialize(right).
  2. Step 2: Null nodes serialize to ,#.
  3. Step 3: strRoot = serialize(root); strSub = serialize(subRoot).
  4. Step 4: Return strRoot.includes(strSub).

Subtree Verification Trace for root = [3, 4, 5], subRoot = [4]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Check root 3 against subRoot 4
Visual state
Values and pointers at this exact step
tree
Root
3
L
4
R
5

Node order shown; add connections to display explicit tree edges.

test: 3
Check / comparison
isSame(3, 4) == false
Decision / next transition
Explore left child 4.
Why this step matters

Step 1: Check root 3 against subRoot 4. Values differ (3 != 4). Recurse to left child 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void serialize(TreeNode* node, string& s) {
10 if (!node) { s += ",#"; return; }
11 s += "," + to_string(node->val);
12 serialize(node->left, s);
13 serialize(node->right, s);
14 }
15 bool isSubtree(TreeNode* root, TreeNode* subRoot) {
16 string s1 = "", s2 = "";
17 serialize(root, s1);
18 serialize(subRoot, s2);
19 return s1.find(s2) != string::npos;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n + m) — String serialization is O(n + m); substring search (KMP / standard) runs in O(n + m).
  • Space complexity: O(n + m) — Serialized strings store O(n + m) characters.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Double DFSO(n * m)O(h)Check isSameTree at each node.Worst-case repetitive checks.
2.Root Value Guarded DFSO(n * m)O(h)Only trigger isSameTree if root.val == subRoot.val.Identical value trees.
3.Serialization with Substring SearchOptimalO(n + m)O(n + m)Serialize with delimiters; test substring inclusion.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • subRoot is identical to root: returns true.
  • subRoot is deeper than root: returns false.
  • Identical values but different shapes: correctly returns false.
  • Super-tree extends beyond subRoot (extra children): returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify that a subtree must include ALL descendants (not just a sub-path).
  2. Mention that while recursive DFS is O(n * m) worst case, serialization with KMP solves it in O(n + m) linear time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must serialized tree strings include specific delimiters (like commas and # for null) when checking for a substring match?

Back to DSA Sheet