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:
root tree is in the range [1, 2000].subRoot tree is in the range [1, 1000].-104 <= root.val <= 104-104 <= subRoot.val <= 104In #572 Subtree of Another Tree, the goal is to determine whether a given binary tree subRoot exists as an exact subtree within another tree root. The most common strategy uses Depth-First Search (DFS). Traverse every node in the main tree and, whenever a node value matches subRoot's root value, perform a recursive comparison to check if the two trees are identical in structure and values.
The comparison step checks whether both nodes are null, values match, and their left and right subtrees also match recursively. If a match is found at any node, the subtree condition is satisfied.
An alternative approach converts both trees into serialized strings using preorder traversal with null markers. Then the problem becomes a substring search where algorithms such as KMP string matching or hashing can efficiently determine if the serialized subRoot appears within the serialized root.
These approaches leverage recursive traversal and structural comparison of binary trees while maintaining manageable time and space complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Tree Comparison | O(n * m) in worst case, where n is nodes in root and m in subRoot | O(h) recursion stack |
| Tree Serialization + String Matching | O(n + m) | O(n + m) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Which approach is better here- recursive or iterative?
If recursive approach is better, can you write recursive function with its parameters?
Two trees <b>s</b> and <b>t</b> 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?
Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)
This approach involves using a recursive function to traverse the root tree and checking for a matching subtree starting from every node. A helper function can be used to check if trees rooted at specific nodes are identical.
Time Complexity: O(N*M), where N is the number of nodes in the root tree and M is the number of nodes in subRoot tree.
Space Complexity: O(min(N, M)), depending on the tree height during recursion.
1#include <stdbool.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9bool isIdentical(struct TreeNode* s, struct TreeNode* t) {
10 if (!s && !t) return true;
11 if (!s || !t) return false;
12 return (s->val == t->val) && isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
13}
14
15bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
16 if (!root) return false;
17 if (isIdentical(root, subRoot)) return true;
18 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
19}The function isIdentical compares two trees recursively to check if they are identical. The main function isSubtree checks the root node against the subRoot using isIdentical and then calls itself recursively on the left and right children of the root node.
Another approach to solving this problem is by converting the trees into their preorder traversal strings with marker symbols for nulls, and then checking if the subRoot string is a substring of the root string.
Time Complexity: O(N + M + N*M), where N and M are the sizes of the trees.
Space Complexity: O(N + M), for the preorder traversal strings.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, subtree and tree comparison problems are common in technical interviews at companies like Google, Amazon, and Meta. They test understanding of recursion, tree traversal, and structural matching in binary trees.
Binary trees are the primary data structure used in this problem. Recursion with depth-first traversal is typically used to compare tree structures efficiently. Some solutions also serialize trees into strings and apply string matching algorithms.
A common optimal approach uses DFS traversal. For every node in the main tree, you check whether the subtree rooted at that node matches the given subRoot using a recursive tree comparison. This ensures the structure and node values match exactly.
Yes, by serializing both trees using preorder traversal with null markers, the subtree problem can be converted into a substring search problem. Efficient string matching algorithms such as KMP can then be applied to check if the serialized subtree appears within the main tree.
This approach serializes both trees using a preorder traversal which handles null nodes explicitly. The serialized string of subRoot is then checked as a substring within that of root.