What is the time complexity of Subtree of Another Tree?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Subtree of Another Tree?

This problem uses Tree, Depth-First Search, String Matching, Binary Tree, Hash Function. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Subtree of Another Tree?

Insight 1: The core idea is to recursively traverse the `root` tree and, for each node, check if the subtree rooted at that node is identical to `subRoot`. Insight 2: We need a separate function to determine if two trees are identical. This function should recursively compare the structure and node values of the two trees.

Which companies ask LeetCode 572. Subtree of Another Tree in interviews?

This problem is frequently asked at Compass, Jump Trading, Morgan Stanley, eBay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Subtree of Another Tree - LeetCode 572 Solution

Subtree of Another Tree - Complete Solution Guide

Subtree of Another Tree is LeetCode problem 572, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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: fal

Detailed Explanation

The problem asks us to determine if a binary tree `subRoot` is a subtree of another binary tree `root`. A subtree is defined as a node in `root` and all of its descendants. Crucially, it must have the exact same structure and node values. The input consists of the root nodes of two binary trees, `root` and `subRoot`. The output should be a boolean value: `true` if `subRoot` is a subtree of `root`, and `false` otherwise. The constraints specify the size and value ranges for the nodes in both trees.

Solution Approach

The solution uses a recursive approach. First, it checks if the `subRoot` is `null`. If it is, it returns `true`. If the `root` is `null` and `subRoot` is not, it returns `false`. Then, it uses a helper function `isSameTree` (or `isSame`) to check if the subtree rooted at the current node of `root` is identical to `subRoot`. If they are identical, it returns `true`. Otherwise, it recursively checks if `subRoot` is a subtree of the left or right subtree of `root`. This effectively explores all possible starting points in `root` for a potential `subRoot` match.

Step-by-Step Algorithm

Step 1: Check if `subRoot` is `null`. If so, return `true` (as an empty tree is a subtree of anything).
Step 2: Check if `root` is `null`. If so, return `false` (as a non-empty tree cannot be a subtree of an empty tree).
Step 3: Call the `isSameTree` (or `isSame`) helper function to check if the `root` tree and `subRoot` tree are identical. If they are, return `true`.
Step 4: If the trees are not identical, recursively call `isSubtree` on the left subtree of `root` and `subRoot`.
Step 5: If Step 4 returns `false`, recursively call `isSubtree` on the right subtree of `root` and `subRoot`.
Step 6: Return the result of the logical OR operation between the results of Step 4 and Step 5. This is because `subRoot` only needs to exist as a subtree in either the left or right subtrees of `root`.

Key Insights

Insight 1: The core idea is to recursively traverse the `root` tree and, for each node, check if the subtree rooted at that node is identical to `subRoot`.
Insight 2: We need a separate function to determine if two trees are identical. This function should recursively compare the structure and node values of the two trees.
Insight 3: The `subRoot` can be considered as a subtree of itself, and an empty `subRoot` tree must always return `true` since an empty tree is a subtree of any other tree.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(n)

Topics

This problem involves: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function.

Companies

Asked at: Compass, Jump Trading, Morgan Stanley, eBay.

Subtree of Another Tree | LeetCode 572

Easy

Tree Depth-First Search String Matching Binary Tree Hash Function

Time: O(m*n)Space: O(n)

Solution Code

Available in:

/**
 * 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) {
        if (root == null) return false;
        if (isSame(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val != subRoot.val) return false;
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 572: Subtree of Another Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search String Matching Binary Tree Hash Function

Companies

CompassJump TradingMorgan StanleyeBay

Stats

Difficulty:Easy

Languages:4

Companies:4

Problem #:572

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Check if `subRoot` is `null`. If so, return `true` (as an empty tree is a subtree of anything).
2
Step 2: Check if `root` is `null`. If so, return `false` (as a non-empty tree cannot be a subtree of an empty tree).
3
Step 3: Call the `isSameTree` (or `isSame`) helper function to check if the `root` tree and `subRoot` tree are identical. If they are, return `true`.
4
Step 4: If the trees are not identical, recursively call `isSubtree` on the left subtree of `root` and `subRoot`.
5
Step 5: If Step 4 returns `false`, recursively call `isSubtree` on the right subtree of `root` and `subRoot`.
6
Step 6: Return the result of the logical OR operation between the results of Step 4 and Step 5. This is because `subRoot` only needs to exist as a subtree in either the left or right subtrees of `root`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The `isSubtree` function can be called at most `n` times (once for each node in `root`). For each call to `isSubtree`, the `isSameTree` function might be called. The `isSameTree` function, in the worst case, traverses all `m` nodes of `subRoot`. Therefore, the overall time complexity is O(m*n) in the worst-case (when every node in `root` has to be checked and is not the correct subtree), and the space complexity is O(h), where h is the height of the root tree. The space complexity reflects the recursion stack's growth. In the worst case (skewed tree), h is n.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

String Serialization

Serialize both trees into strings, including special markers for `null` nodes. Then, check if the serialized `subRoot` string is a substring of the serialized `root` string. This works because if `subRoot` is a subtree of `root`, its serialized representation must be present within the serialized representation of `root` when starting from the correct node.

Time: O(n + m), where n is the number of nodes in `root` and m is the number of nodes in `subRoot`. String searching (e.g., KMP algorithm) takes O(n+m).Space: O(n + m), to store the serialized strings.

Trade-offs: This approach might be faster if string searching algorithms are highly optimized but requires extra space for the string representations. However, simple string matching can have O(n*m) complexity. Also, you need to be very careful with serialization logic (e.g. using unique delimiters), since simply checking substring presence might cause false positives.

✨

Key Insights

1Insight 1: The core idea is to recursively traverse the `root` tree and, for each node, check if the subtree rooted at that node is identical to `subRoot`.
2Insight 2: We need a separate function to determine if two trees are identical. This function should recursively compare the structure and node values of the two trees.
3Insight 3: The `subRoot` can be considered as a subtree of itself, and an empty `subRoot` tree must always return `true` since an empty tree is a subtree of any other tree.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: `subRoot` is `null`. The solution correctly returns `true` because an empty tree is considered a subtree of any tree.
Edge case 2: `root` is `null` but `subRoot` is not `null`. The solution correctly returns `false` because a non-empty tree cannot be a subtree of an empty tree.
Edge case 3: Both `root` and `subRoot` are `null`. `isSameTree` correctly handles this and returns true, and consequently `isSubtree` as well (after first `root` check in `isSubtree`).
Edge case 4: `root` and `subRoot` are structurally the same but have different values at some nodes. The `isSameTree` function will correctly return `false`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking for `null` nodes in the `isSameTree` function, which can lead to `NullPointerException` or incorrect comparisons.

✗Common mistake 2: Incorrectly implementing the `isSameTree` function, especially regarding the logical AND/OR operators. The condition `p.val != q.val` should immediately return `false`, as this means the trees are not identical.

✗Common mistake 3: Forgetting to handle the case where the `subRoot` is `null`, leading to incorrect results or errors.

✗Common mistake 4: Failing to recognize the recursive nature of the problem and trying to solve it iteratively, which would be significantly more complex for this problem.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting duplicate directory structures in a file system. Each directory can be viewed as a tree, and identifying duplicate sub-directories is equivalent to finding subtrees.

🏦Real-world scenario 2: Analyzing XML or JSON data structures for specific nested elements or patterns. The XML/JSON structure can be represented as a tree, and the problem becomes searching for a specific subtree within the larger structure.

🎮Real-world scenario 3: Code plagiarism detection - Abstract Syntax Trees (ASTs) can represent code structure. Finding subtree matches in ASTs can indicate duplicated or copied code segments.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Subtree of Another Tree"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?