This problem requires verifying if a given binary tree exists entirely as a subtree within another tree. You need to traverse the main tree and compare each node's subtree against the target subRoot, ensuring both structure and node values match exactly. Recursive depth-first search combined with optional hash-based subtree comparisons offers an efficient solution, while careful null checks prevent misalignment errors.
Problem Statement
Given two binary trees, root and subRoot, determine whether subRoot is exactly a subtree of root. A subtree is defined as any node in root and all of its descendants matching subRoot's structure and node values.
Return true if there exists a node in root where the subtree rooted at that node is identical to subRoot. Otherwise, return false. For example, root = [3,4,5,1,2], subRoot = [4,1,2] should return true, whereas root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] returns false.
Examples
Example 1
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example details omitted.
Example 2
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Example details omitted.
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
Solution Approach
Recursive Comparison
Traverse each node in root using depth-first search and check if the subtree matches subRoot exactly by recursively comparing node values and child structure.
Hashing Subtrees for Optimization
Use a hash function to encode each subtree's structure and values, then compare hashes to quickly detect matches and reduce repeated subtree comparisons.
Iterative Traversal Alternative
An iterative approach using a stack or queue can simulate recursive DFS traversal to compare potential matching subtrees, useful if recursion depth might be an issue.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity can reach O(m*n) in the worst case for comparing m nodes in root with n nodes in subRoot, but hashing or pruning identical subtrees can reduce comparisons. Space complexity depends on recursion stack depth or storage for subtree hashes.
What Interviewers Usually Probe
- Asks whether recursion or iterative traversal is preferable for subtree comparison.
- Checks if null node handling is correctly implemented in the DFS solution.
- Mentions optimization using subtree serialization or hashing techniques.
Common Pitfalls or Variants
Common pitfalls
- Failing to check both left and right children for exact match leading to false positives.
- Confusing a node with identical value as a valid subtree without matching the full structure.
- Exceeding recursion limits on deeply nested trees without iterative fallback.
Follow-up variants
- Determine if a tree is a mirror subtree of another, requiring reversed child comparisons.
- Count the total number of occurrences where subRoot appears as a subtree within root.
- Check if subRoot appears as a subtree in a forest of multiple disconnected trees.
How GhostInterview Helps
- Highlights exact nodes in root where subRoot matches or fails for efficient debugging.
- Suggests optimal traversal order and subtree hashing strategies tailored to this problem's pattern.
- Provides instant comparison logic for left and right children to avoid common misalignment errors.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to check if one tree is a subtree of another?
Use recursive DFS traversal and optional subtree hashing to compare structure and node values efficiently.
Can iterative traversal replace recursion for the subtree check?
Yes, iterative DFS or BFS using a stack or queue can replace recursion and prevent stack overflow in deep trees.
Why do some implementations give false positives?
False positives often occur when only node values are compared without checking the full subtree structure.
How does hashing improve subtree comparison?
Hashing encodes subtree structures and values into a single representation, allowing quick equality checks instead of repeated recursive comparison.
Does this problem pattern involve string matching?
Yes, comparing serialized or hashed subtrees is similar to string matching, making pattern detection efficient.
Need direct help with Subtree of Another Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Subtree of Another Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Calculate the sum of the binary tree's node tilts using tree traversal and state tracking.
Open problem page#538 Convert BST to Greater TreeConvert a BST into a Greater Tree by updating each node’s value with the sum of all greater values in the tree.
Open problem page#606 Construct String from Binary TreeGiven a binary tree, construct a string representation based on preorder traversal while adhering to specific formatting rules.
Open problem page