Subtree of Another Tree — Solution in Python, Java & C++
Subtree of Another Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Subtree of Another Tree is an easy coding problem on depth-first search, trees and string matching, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees, String Matching
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the roots root and subRoot of two binary trees. Return true if root contains a subtree that is identical to subRoot — the same shape and the same values — and false otherwise.
A subtree of root is some node of root together with all of its descendants; root is a subtree of itself.
Example 1
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Explanation: The node 4 of `root`, with its children 1 and 2, matches `subRoot` exactly.
Example 2
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Explanation: The node 4 has the right values on top, but its subtree also contains the 0 under 2 — a subtree must include every descendant.
Example 3
Input: root = [1,1], subRoot = [1]
Output: true
Explanation: The leaf 1 matches; the root 1 does not, because it has a child.
Constraints
The number of nodes inrootis in the range [1, 2000]The number of nodes insubRootis in the range [1, 1000]-10^4 <= root.val <= 10^4-10^4 <= subRoot.val <= 10^4
Hints for Subtree of Another Tree
Hint 1
Use the Same Tree check as a building block: is the tree rooted at this node identical to
subRoot?Hint 2
Try that check at every node of
root— if any succeeds, the answer istrue.Hint 3
Matching tops are not enough: the comparison must fail when either side has a node the other lacks, all the way down to the leaves.
How to solve Subtree of Another Tree
subRoot occurs in root exactly when some node of root roots a tree identical to subRoot. Walk every node of root and run an identical-trees check from it.
Approach
same(a, b): both null →true; one null →false; otherwise equal values andsameon both child pairs.isSubtree(node, sub): ifnodeis null returnfalse.- If
same(node, sub)returntrue. - Otherwise return
isSubtree(node.left, sub) || isSubtree(node.right, sub).
Why it works
A subtree is determined by its top node, so trying every node of root as the top covers every candidate, and same accepts a candidate only if it matches subRoot node for node including where each one ends.
Complexity
- Time —
O(n · m) in the worst case, for n and m nodes; serialising both trees and string-matching brings it to O(n + m) - Space —
O(h) recursion depth
Pitfalls
- Checking only that
subRoot's values appear starting at some node accepts a match with extra descendants (second example). - Serialising without null markers (or without separators between values) makes different trees look alike, e.g.
12vs12.
Reference solution
Python
from typing import Optional
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def same(a, b):
if a is None or b is None:
return a is b
return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
def walk(node):
if node is None:
return False
return same(node, subRoot) or walk(node.left) or walk(node.right)
return walk(root)Java
public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
return sameShape(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
static boolean sameShape(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == b;
return a.val == b.val && sameShape(a.left, b.left) && sameShape(a.right, b.right);
}C++
bool sameShape(TreeNode* a, TreeNode* b) {
if (!a || !b) return a == b;
return a->val == b->val && sameShape(a->left, b->left) && sameShape(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
return sameShape(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}JavaScript
var isSubtree = function(root, subRoot) {
if (root === null) return false;
return sameShape(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};
var sameShape = function(a, b) {
if (a === null || b === null) return a === b;
return a.val === b.val && sameShape(a.left, b.left) && sameShape(a.right, b.right);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals