Language Selection
Choose your preferred programming language
Showing: Python
Subtree of Another Tree
Problem Statement
You are given the roots of two binary trees, root and subRoot. Return true if root contains a node whose subtree is identical to subRoot, and false otherwise.
The subtree of a node is that node together with all of its descendants. Identical means the same shape and the same value at every position. So a match must line up all the way to the leaves: if the candidate node in root has extra children below the part that matches, it is not a match. Every tree counts as a subtree of itself.
Examples
Example 1:
Input: root = [7,2,9,1,4], subRoot = [2,1,4]
Output: true
Explanation: The left child of 7 is a node 2 with children 1 and 4, which is exactly subRoot.
Example 2:
Input: root = [7,2,9,1,4,null,null,null,null,3], subRoot = [2,1,4]
Output: false
Explanation: The node 2 still has children 1 and 4, but the 4 now has a left child 3.
The subtree rooted at 2 is [2,1,4,null,null,3], which is not identical to subRoot.
Example 3:
Input: root = [6,6,null,6], subRoot = [6,6]
Output: true
Explanation: root is a chain of three 6s down the left side. The middle 6 with its single
left child 6 matches subRoot. The top 6 does not, because its subtree has three nodes.
Constraints
roothas between1and2000nodes.subRoothas between1and1000nodes.-10^4 <= Node.val <= 10^4
Approach 1: DFS with a Same-Tree Check at Every Node
Algorithm
A match has to start at some node of root. So try every node as a starting point and ask whether the tree hanging from it is identical to subRoot, using the Same Tree check.
- If
rootis null, returnfalse: an empty tree contains no node to start from. - If
isSameTree(root, subRoot), returntrue. - Otherwise return
isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).
isSameTree(p, q) returns true when both are null, false when only one is null or the values differ, and otherwise checks both pairs of children.
root can be a chain 2000 nodes deep. The Python version raises the recursion limit, since Python’s default of 1000 frames is too low for that; the other languages handle a few thousand frames with their default stacks.
Implementation
Python:
# 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
import sys
from typing import Optional
# root can be 2000 levels deep, beyond Python's default limit of 1000 frames
sys.setrecursionlimit(10000)
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
# Ran out of nodes to start a match from
if root is None:
return False
# Try a match starting here, then in each child's subtree
if self.isSameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if p is None or q is None or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Java:
/**
* 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) {
// Ran out of nodes to start a match from
if (root == null) {
return false;
}
// Try a match starting here, then in each child's subtree
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
Go:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
// Ran out of nodes to start a match from
if root == nil {
return false
}
// Try a match starting here, then in each child's subtree
if isSameTree(root, subRoot) {
return true
}
return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
JavaScript:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} subRoot
* @return {boolean}
*/
var isSubtree = function(root, subRoot) {
// Ran out of nodes to start a match from
if (root === null) {
return false;
}
// Try a match starting here, then in each child's subtree
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};
function isSameTree(p, q) {
if (p === null && q === null) {
return true;
}
if (p === null || q === null || p.val !== q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
C#:
/**
* 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) {
// Ran out of nodes to start a match from
if (root == null) {
return false;
}
// Try a match starting here, then in each child's subtree
if (IsSameTree(root, subRoot)) {
return true;
}
return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
}
private bool IsSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}
}
C++:
/**
* 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) {
// Ran out of nodes to start a match from
if (root == nullptr) {
return false;
}
// Try a match starting here, then in each child's subtree
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
private:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p == nullptr || q == nullptr || p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
Complexity Analysis
- Time: O(m * n), where m is the number of nodes in
rootand n the number insubRoot. The same-tree check runs from each of the m nodes and can compare up to n pairs before failing, for example when both trees are long chains of the same value. - Space: O(h), where h is the height of
root, for the recursion stack. A same-tree call starting at depth d never goes deeper than the bottom ofroot, so the stack never holds more than about h frames.
Approach 2: Serialize with Null Markers + KMP (Optimal)
Algorithm
Write each tree as its preorder sequence of values, adding a null marker for every missing child. With the null markers, the sequence describes the tree exactly, and it has a useful property: the subtree rooted at any node is a contiguous block of its tree’s sequence, starting at that node’s value. So subRoot is a subtree of root exactly when subRoot’s sequence appears as a contiguous block inside root’s sequence.
Two details make this safe:
- Null markers are required. Without them,
[2,1](1 on the left) and[2,null,1](1 on the right) both give the sequence2, 1. - Compare whole values, not characters. If you build strings,
"12"contains"2". Working with a list of integers avoids that; a string version must put a separator before every value (for example",12"versus",2").
Finding a block inside a sequence is string matching, and KMP does it in linear time.
- Serialize both trees in preorder with null markers. Use an explicit stack so a 2000-deep tree cannot overflow the call stack: pop a node; if it is null, emit the marker; otherwise emit its value and push its right child, then its left child.
- Build the KMP prefix table (
lps) for thesubRootsequence:lps[i]is the length of the longest proper prefix ofpattern[0..i]that is also a suffix of it. - Scan the
rootsequence with KMP. On a mismatch, fall back usinglpsinstead of restarting. If the matched length reaches the pattern length, returntrue. - Return
falseif the scan ends without a full match.
The null marker must never equal a real value. Values stay within ±10^4, so Python and JavaScript use None/null and the typed languages use the minimum 32-bit integer.
Implementation
Python:
# 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
from typing import List, Optional
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
return self._contains(self._serialize(root), self._serialize(subRoot))
def _serialize(self, root: Optional[TreeNode]) -> List[Optional[int]]:
# Preorder values with None for each missing child; explicit stack, so deep trees are safe
tokens = []
stack = [root]
while stack:
node = stack.pop()
if node is None:
tokens.append(None)
continue
tokens.append(node.val)
# Push right first so the left subtree is emitted first
stack.append(node.right)
stack.append(node.left)
return tokens
def _contains(self, text: List[Optional[int]], pattern: List[Optional[int]]) -> bool:
# lps[i]: longest proper prefix of pattern[:i + 1] that is also its suffix
lps = [0] * len(pattern)
k = 0
for i in range(1, len(pattern)):
while k > 0 and pattern[i] != pattern[k]:
k = lps[k - 1]
if pattern[i] == pattern[k]:
k += 1
lps[i] = k
# KMP scan: on a mismatch, fall back in the pattern instead of restarting
k = 0
for token in text:
while k > 0 and token != pattern[k]:
k = lps[k - 1]
if token == pattern[k]:
k += 1
if k == len(pattern):
return True
return False
Java:
/**
* 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;
* }
* }
*/
import java.util.ArrayList;
import java.util.List;
class Solution {
// Marks a missing child; node values never come near Integer.MIN_VALUE
private static final int NULL_MARK = Integer.MIN_VALUE;
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
return contains(serialize(root), serialize(subRoot));
}
private int[] serialize(TreeNode root) {
List<Integer> tokens = new ArrayList<>();
// An ArrayList used as a stack, because it accepts null children
List<TreeNode> stack = new ArrayList<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.remove(stack.size() - 1);
if (node == null) {
tokens.add(NULL_MARK);
continue;
}
tokens.add(node.val);
// Push right first so the left subtree is emitted first
stack.add(node.right);
stack.add(node.left);
}
int[] result = new int[tokens.size()];
for (int i = 0; i < result.length; i++) {
result[i] = tokens.get(i);
}
return result;
}
private boolean contains(int[] text, int[] pattern) {
// lps[i]: longest proper prefix of pattern[0..i] that is also its suffix
int[] lps = new int[pattern.length];
for (int i = 1, k = 0; i < pattern.length; i++) {
while (k > 0 && pattern[i] != pattern[k]) {
k = lps[k - 1];
}
if (pattern[i] == pattern[k]) {
k++;
}
lps[i] = k;
}
// KMP scan: on a mismatch, fall back in the pattern instead of restarting
int k = 0;
for (int token : text) {
while (k > 0 && token != pattern[k]) {
k = lps[k - 1];
}
if (token == pattern[k]) {
k++;
if (k == pattern.length) {
return true;
}
}
}
return false;
}
}
Go:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
import "math"
// Marks a missing child; node values never come near math.MinInt32
const nullMark = math.MinInt32
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
return containsSeq(serialize(root), serialize(subRoot))
}
func serialize(root *TreeNode) []int {
tokens := []int{}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node == nil {
tokens = append(tokens, nullMark)
continue
}
tokens = append(tokens, node.Val)
// Push right first so the left subtree is emitted first
stack = append(stack, node.Right, node.Left)
}
return tokens
}
func containsSeq(text, pattern []int) bool {
// lps[i]: longest proper prefix of pattern[:i+1] that is also its suffix
lps := make([]int, len(pattern))
for i, k := 1, 0; i < len(pattern); i++ {
for k > 0 && pattern[i] != pattern[k] {
k = lps[k-1]
}
if pattern[i] == pattern[k] {
k++
}
lps[i] = k
}
// KMP scan: on a mismatch, fall back in the pattern instead of restarting
k := 0
for _, token := range text {
for k > 0 && token != pattern[k] {
k = lps[k-1]
}
if token == pattern[k] {
k++
if k == len(pattern) {
return true
}
}
}
return false
}
JavaScript:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} subRoot
* @return {boolean}
*/
var isSubtree = function(root, subRoot) {
return containsSeq(serialize(root), serialize(subRoot));
};
// Preorder values with null for each missing child; explicit stack, so deep trees are safe
function serialize(root) {
const tokens = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node === null) {
tokens.push(null);
continue;
}
tokens.push(node.val);
// Push right first so the left subtree is emitted first
stack.push(node.right, node.left);
}
return tokens;
}
function containsSeq(text, pattern) {
// lps[i]: longest proper prefix of pattern[0..i] that is also its suffix
const lps = new Array(pattern.length).fill(0);
for (let i = 1, k = 0; i < pattern.length; i++) {
while (k > 0 && pattern[i] !== pattern[k]) {
k = lps[k - 1];
}
if (pattern[i] === pattern[k]) {
k++;
}
lps[i] = k;
}
// KMP scan: on a mismatch, fall back in the pattern instead of restarting
let k = 0;
for (const token of text) {
while (k > 0 && token !== pattern[k]) {
k = lps[k - 1];
}
if (token === pattern[k]) {
k++;
if (k === pattern.length) {
return true;
}
}
}
return false;
}
C#:
/**
* 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;
* }
* }
*/
using System.Collections.Generic;
public class Solution {
// Marks a missing child; node values never come near int.MinValue
private const int NullMark = int.MinValue;
public bool IsSubtree(TreeNode root, TreeNode subRoot) {
return Contains(Serialize(root), Serialize(subRoot));
}
private List<int> Serialize(TreeNode root) {
var tokens = new List<int>();
var stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
if (node == null) {
tokens.Add(NullMark);
continue;
}
tokens.Add(node.val);
// Push right first so the left subtree is emitted first
stack.Push(node.right);
stack.Push(node.left);
}
return tokens;
}
private bool Contains(List<int> text, List<int> pattern) {
// lps[i]: longest proper prefix of pattern[0..i] that is also its suffix
int[] lps = new int[pattern.Count];
for (int i = 1, k = 0; i < pattern.Count; i++) {
while (k > 0 && pattern[i] != pattern[k]) {
k = lps[k - 1];
}
if (pattern[i] == pattern[k]) {
k++;
}
lps[i] = k;
}
// KMP scan: on a mismatch, fall back in the pattern instead of restarting
int matched = 0;
foreach (int token in text) {
while (matched > 0 && token != pattern[matched]) {
matched = lps[matched - 1];
}
if (token == pattern[matched]) {
matched++;
if (matched == pattern.Count) {
return true;
}
}
}
return false;
}
}
C++:
/**
* 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) {}
* };
*/
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
return contains(serialize(root), serialize(subRoot));
}
private:
// Marks a missing child; node values never come near INT_MIN
static constexpr int NULL_MARK = INT_MIN;
vector<int> serialize(TreeNode* root) {
vector<int> tokens;
vector<TreeNode*> stack{root};
while (!stack.empty()) {
TreeNode* node = stack.back();
stack.pop_back();
if (node == nullptr) {
tokens.push_back(NULL_MARK);
continue;
}
tokens.push_back(node->val);
// Push right first so the left subtree is emitted first
stack.push_back(node->right);
stack.push_back(node->left);
}
return tokens;
}
bool contains(const vector<int>& text, const vector<int>& pattern) {
// lps[i]: longest proper prefix of pattern[0..i] that is also its suffix
vector<size_t> lps(pattern.size(), 0);
for (size_t i = 1, k = 0; i < pattern.size(); i++) {
while (k > 0 && pattern[i] != pattern[k]) {
k = lps[k - 1];
}
if (pattern[i] == pattern[k]) {
k++;
}
lps[i] = k;
}
// KMP scan: on a mismatch, fall back in the pattern instead of restarting
size_t k = 0;
for (int token : text) {
while (k > 0 && token != pattern[k]) {
k = lps[k - 1];
}
if (token == pattern[k]) {
k++;
if (k == pattern.size()) {
return true;
}
}
}
return false;
}
};
Complexity Analysis
- Time: O(m + n). Each serialization visits every node once and emits
2 * nodes + 1tokens. Building thelpstable is O(n) and the KMP scan is O(m), because the fallback steps never exceed the forward steps. - Space: O(m + n) for the two token sequences and the
lpstable. The explicit stack holds at most O(h) entries.
Key Insights
- A subtree match must reach the leaves. Matching the top part of
root’s subtree is not enough; any extra node below makes it a different tree. That is why both approaches compare null children too. - Reuse Same Tree. Approach 1 is just “is the tree at this node the same as
subRoot?” asked at every node. - Preorder with null markers is a faithful encoding. It identifies the tree exactly, and each subtree becomes one contiguous block. That turns a tree problem into substring search.
- Token boundaries matter. Comparing integers (or delimited strings) stops
2from matching the tail of12and-4from matching4. - KMP gives the linear bound. A naive block search on the sequences would be O(m * n) again; KMP never re-reads text it has already matched.
Edge Cases
rootandsubRootare identical: returntrue; a tree is its own subtree.subRootmatches the top of a subtree that has extra descendants (Example 2): returnfalse.- Repeated values, like chains of the same number (Example 3): the first node with the right value may not be the match, so keep searching.
subRootis a single node: it matches only a leaf with that value, not an inner node.subRootlarger thanroot: can never match; both approaches returnfalse.- Values that are digit-suffixes of each other, like
2and12, or4and-4: only a problem for undelimited string serializations. - A 2000-node chain: recursion depth reaches 2000, which needs Python’s recursion limit raised; Approach 2 uses an explicit stack.
Common Mistakes
- Matching only values, not structure. Finding a node with
subRoot’s value and comparing a few children is not enough. - Stopping after the first value match. If the first node with the root value is not a match, other nodes with the same value may be.
- Serializing without null markers. Different shapes then produce the same sequence.
- Building strings without separators and calling
contains, so"12"matches"2". - Using a library substring search and claiming O(m + n). Many built-in
indexOf/findimplementations are worst-case O(m * n); use KMP (or Z-function or rolling hash) for a guaranteed bound.
Interview Tips
- Start with Approach 1. It is short, uses Same Tree as a helper, and is what most interviewers expect for an Easy problem.
- State the O(m * n) worst case honestly and give the example: long chains of equal values.
- Offer serialization + KMP as the upgrade, explaining why null markers and token boundaries are needed.
- Mention tree hashing (Merkle hashing) as another linear-time idea: hash each subtree from its children’s hashes and compare hashes, then confirm a hash match with a real comparison.
- Test with Example 2’s trap: a matching top part with extra nodes underneath.
Follow-up Questions
- What if subtrees only need to match the top part, ignoring extra descendants? Change the base case: reaching a null in
subRootcounts as a match regardless of the other tree. - Find every node where
subRootoccurs. Keep scanning after each KMP match and map token positions back to nodes. - Find duplicate subtrees within one tree (LeetCode 652). Serialize every subtree bottom-up and count the serializations in a hash map.
- How would you check many patterns against one big tree? Precompute a hash or canonical ID for every subtree of the big tree once, then look up each pattern’s hash.
- What changes for very deep trees? Approach 1 needs explicit stacks for both walks; Approach 2 already serializes iteratively.