Subtree of Another Tree solution and explanation
Google
9 more videos on this problem
Subtree of Another Tree - Leetcode 572 - PythonNeetCode · 14:15 · 261K views
Subtree of Another Tree (LeetCode 572) | Full solution with examples | Study AlgorithmsNikhil Lohia · 14:47 · 15K views
Subtree of Another Tree - Leetcode 572 - Trees (Python)Greg Hogg · 6:01 · 13K views
572. Subtree of Another Tree - LeetCode Java SolutionCode with Carter · 6:55 · 2K views
LeetCode 572 Subtree of Another Tree | Blind 75Code In Motion · 12:02 · 1K views
Subtree of Another Tree - LeetCode 572 - Python #leetcode #blind75 #binarytree #subtreeofanothertreeDeepti Talesra · 11:50 · 1K views
LeetCode 572: Subtree of Another Tree | More Recursive DFSAbstracted Away · 5:43 · 1K views
Subtree Of Another Tree | LeetCode 572 (Easy)Destination FAANG · 8:26 · 1K views
Subtree of Another Subtree - Coding Interview Question - LeetCode 572AlgoJS · 5:10 · 1K views
LeetCode Tutorial - 572. Subtree of Another TreeMax Li · 3:29 · 961 views
The problem
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
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104 <= root.val <= 104-104 <= subRoot.val <= 104
Approach overview
Problem Overview: Given two binary trees root and subRoot, determine whether subRoot appears as a subtree inside root. A subtree means a node in the main tree whose entire structure and node values exactly match subRoot.
Approach 1: Recursive Tree Traversal (DFS Comparison) (Time: O(n * m), Space: O(h))
This approach walks through every node in the main tree and checks if the subtree starting at that node is identical to subRoot. For each node in root, run a second DFS that compares both trees node-by-node. The comparison verifies three things: values match, left children match, and right children match. If any comparison fails, continue scanning other nodes in the main tree.
The key idea is separating the logic into two DFS functions: one that iterates through the main tree and another that checks structural equality. In the worst case, you compare the subtree with every node of the main tree, giving O(n * m) time where n and m are the sizes of the two trees. Recursion depth depends on tree height, so space complexity is O(h). This method is straightforward and commonly used in interviews involving tree and depth-first search problems.
Approach 2: Preorder String Comparison (Tree Serialization) (Time: O(n + m), Space: O(n + m))
This technique converts both trees into strings using preorder traversal. During serialization, include special markers for null nodes so different structures produce different strings. For example, append # whenever a null child appears. Without null markers, different trees could produce identical sequences.
Once both trees are serialized, the subtree check becomes a substring problem. If the preorder string of subRoot appears inside the preorder string of root, the subtree exists. Efficient substring search algorithms such as KMP reduce the complexity to O(n + m). The trade-off is extra memory to store the serialized strings. This method blends ideas from binary tree traversal and string matching algorithms.
Recommended for interviews: The recursive DFS comparison is usually what interviewers expect first because it clearly demonstrates understanding of tree traversal and structural equality checks. Mentioning the serialization approach afterward shows deeper knowledge and awareness of optimization techniques that convert tree problems into string matching problems.
Approach 1: Recursive Tree Traversal
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.
class Solution:
def isSubtree(self, root, subRoot):
if not root:
return False
if self.isIdentical(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def isIdentical(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isIdentical(s.left, t.left) and self.isIdentical(s.right, t.right)class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (isIdentical(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isIdentical(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && isIdentical(s.left, t.left) && isIdentical(s.right, t.right);
}
}#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
};
bool isIdentical(TreeNode* s, TreeNode* t) {
if (!s && !t) return true;
if (!s || !t) return false;
return (s->val == t->val) && isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
if (isIdentical(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}var isSubtree = function(root, subRoot) {
if (!root) return false;
if (isIdentical(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};
var isIdentical = function(s, t) {
if (!s && !t) return true;
if (!s || !t) return false;
return s.val === t.val && isIdentical(s.left, t.left) && isIdentical(s.right, t.right);
};#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isIdentical(struct TreeNode* s, struct TreeNode* t) {
if (!s && !t) return true;
if (!s || !t) return false;
return (s->val == t->val) && isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if (!root) return false;
if (isIdentical(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}public class Solution {
public bool IsSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (IsIdentical(root, subRoot)) return true;
return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
}
private bool IsIdentical(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && IsIdentical(s.left, t.left) && IsIdentical(s.right, t.right);
}
}The solution follows a recursive approach where isIdentical checks whether the trees rooted at the current nodes of root and subRoot are the same. If a match is found, it returns true immediately; otherwise, it checks left and right subtree relations.
Time Complexity: O(N*M), with N and M as the sizes of root and subRoot trees.
Space Complexity: O(min(N, M)) for the recursion depth.
Approach 2: Preorder String Comparison
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.
class Solution:
def isSubtree(self, root, subRoot):
return self.preorder(root).find(self.preorder(subRoot)) != -1
def preorder(self, node):
if not node:
return "null "
return str(node.val) + " " + self.preorder(node.left) + self.preorder(node.right)class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
String rootStr = preorder(root, new StringBuilder()).toString();
String subRootStr = preorder(subRoot, new StringBuilder()).toString();
return rootStr.contains(subRootStr);
}
private StringBuilder preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("null ");
return sb;
}
sb.append(node.val).append(' ');
preorder(node.left, sb);
preorder(node.right, sb);
return sb;
}
}#include <string>
#include <sstream>
struct TreeNode {
int val;
TreeNode *left, *right;
};
void getPreorder(TreeNode* node, std::ostringstream& out) {
if (node == NULL) {
out << "null ";
return;
}
out << node->val << " ";
getPreorder(node->left, out);
getPreorder(node->right, out);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
std::ostringstream rootStream, subRootStream;
getPreorder(root, rootStream);
getPreorder(subRoot, subRootStream);
return rootStream.str().find(subRootStream.str()) != std::string::npos;
}var isSubtree = function(root, subRoot) {
const rootStr = preorder(root).join(' ');
const subRootStr = preorder(subRoot).join(' ');
return rootStr.indexOf(subRootStr) !== -1;
};
var preorder = function(node) {
if (!node) {
return ['null'];
}
return [node.val.toString(), ...preorder(node.left), ...preorder(node.right)];
};#include <stdbool.h>
#include <string.h>
#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left, *right;
};
void preorder(struct TreeNode* node, char *s) {
if (node == NULL) {
strcat(s, "null ");
return;
}
char buffer[12];
sprintf(buffer, "%d ", node->val);
strcat(s, buffer);
preorder(node->left, s);
preorder(node->right, s);
}
bool isSubstring(char* s1, char* s2) {
return strstr(s1, s2) != NULL;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
char rootString[10000] = "";
char subRootString[10000] = "";
preorder(root, rootString);
preorder(subRoot, subRootString);
return isSubstring(rootString, subRootString);
}public class Solution {
public bool IsSubtree(TreeNode root, TreeNode subRoot) {
string rootStr = Preorder(root, new System.Text.StringBuilder()).ToString();
string subRootStr = Preorder(subRoot, new System.Text.StringBuilder()).ToString();
return rootStr.Contains(subRootStr);
}
private StringBuilder Preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.Append("null ");
return sb;
}
sb.Append(node.val).Append(' ');
Preorder(node.left, sb);
Preorder(node.right, sb);
return sb;
}
}The Python solution uses preorder traversal to obtain a string representation of both trees and checks the inclusion of subRoot's string representation within root's string.
Time Complexity: O(N + M + N*M).
Space Complexity: O(N + M), for traversal strings.
Approach 3: DFS
We define a helper function same(p, q) to determine whether the tree rooted at p and the tree rooted at q are identical. If the root values of the two trees are equal, and their left and right subtrees are also respectively equal, then the two trees are identical.
In the isSubtree(root, subRoot) function, we first check if root is null. If it is, we return false. Otherwise, we check if root and subRoot are identical. If they are, we return true. Otherwise, we recursively check if the left or right subtree of root contains subRoot.
The time complexity is O(n times m), and the space complexity is O(n). Here, n and m are the number of nodes in the trees root and subRoot, respectively.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
const same = (p: TreeNode | null, q: TreeNode | null): boolean => {
if (!p || !q) {
return p === q;
}
return p.val === q.val && same(p.left, q.left) && same(p.right, q.right);
};
if (!root) {
return false;
}
return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
var same func(p, q *TreeNode) bool
same = func(p, q *TreeNode) bool {
if p == nil || q == nil {
return p == q
}
return p.Val == q.Val && same(p.Left, q.Left) && same(p.Right, q.Right)
}
if root == nil {
return false
}
return same(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_subtree(
root: Option<Rc<RefCell<TreeNode>>>,
sub_root: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
if root.is_none() {
return false;
}
Self::same(&root, &sub_root)
|| Self::is_subtree(
root.as_ref().unwrap().borrow().left.clone(),
sub_root.clone(),
)
|| Self::is_subtree(
root.as_ref().unwrap().borrow().right.clone(),
sub_root.clone(),
)
}
fn same(p: &Option<Rc<RefCell<TreeNode>>>, q: &Option<Rc<RefCell<TreeNode>>>) -> bool {
match (p, q) {
(None, None) => true,
(Some(p), Some(q)) => {
let p = p.borrow();
let q = q.borrow();
p.val == q.val && Self::same(&p.left, &q.left) && Self::same(&p.right, &q.right)
}
_ => false,
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Tree Traversal | Time Complexity: O(N*M), with N and M as the sizes of root and subRoot trees. |
| Preorder String Comparison | Time Complexity: O(N + M + N*M). |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Traversal (DFS comparison) | O(n * m) | O(h) | Most common interview solution. Easy to implement and works well for moderate tree sizes. |
| Preorder String Serialization + Substring Search | O(n + m) | O(n + m) | When you want a more optimized approach by converting the tree comparison into a string matching problem. |
Frequently asked questions
Is Subtree of Another Tree easy or hard?
Subtree of Another Tree is classified as an Easy problem on LeetCode with about a 50% acceptance rate. The logic is straightforward once you understand how to compare two binary trees recursively.
Subtree of Another Tree Python/Java solution
In Python or Java, the typical solution defines a helper function that checks whether two trees are identical using recursion. The main function traverses the root tree and calls this helper whenever node values match the root of subRoot.
How to solve Subtree of Another Tree in O(n)?
Serialize both trees using preorder traversal while inserting markers for null nodes. Then check if the serialized string of subRoot appears inside the serialized string of root. Using a linear string matching algorithm like KMP makes the overall complexity O(n + m).
What is the best approach for Subtree of Another Tree?
The most common approach uses recursive DFS. Traverse every node of the main tree and run a second DFS to check if the subtree rooted at that node is identical to subRoot. This method is simple to implement and works well in interviews, though the worst-case time complexity is O(n * m).
Is Subtree of Another Tree asked at Google/Amazon/Meta?
Subtree comparison problems frequently appear in interviews at major tech companies such as Amazon, Google, and Meta. They test understanding of binary tree traversal, recursion, and structural equality checks, which are core tree interview concepts.
What data structure is used in Subtree of Another Tree?
The problem primarily uses a binary tree data structure. Solutions rely on depth-first search recursion to traverse nodes, and some optimized methods additionally use strings or hash-based matching after serializing the tree structure.
What is the time complexity of Subtree of Another Tree?
The DFS comparison approach runs in O(n * m) time where n is the number of nodes in the main tree and m is the number of nodes in the subtree. An optimized solution using preorder serialization and efficient substring search such as KMP can reduce the time complexity to O(n + m).