What is the time complexity of Find Duplicate Subtrees?

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

What data structures are used to solve Find Duplicate Subtrees?

This problem uses Hash Table, Tree, Depth-First Search, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find Duplicate Subtrees?

Insight 1: We need a way to uniquely identify each subtree's structure and values. This is crucial for comparing subtrees to detect duplicates. Insight 2: Serializing the subtree into a string allows us to use a hash table (dictionary) to efficiently track the occurrence of each unique subtree structure.

Which companies ask LeetCode 652. Find Duplicate Subtrees in interviews?

This problem is frequently asked at PhonePe, Yandex.

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

Find Duplicate Subtrees - LeetCode 652 Solution

Find Duplicate Subtrees - Complete Solution Guide

Find Duplicate Subtrees is LeetCode problem 652, a Medium 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 root of a binary tree, return all duplicate subtrees . For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with the same node values . Example 1: Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] Example 2: Input: root = [2,1,1] Output: [[1]] Example 3: Input: root = [2,2,2,3,null,3,null] Output: [[2,3],[3]] Constraints: The number of the nodes in the tree will be in the ra

Detailed Explanation

The problem asks us to find all duplicate subtrees within a given binary tree. A duplicate subtree is defined as a subtree that has the same structure and node values as another subtree within the original tree. The task is to return a list containing the root nodes of all such duplicate subtrees. For each distinct type of duplicate subtree, we only need to return the root node of any *one* instance of it. This means if the same subtree appears multiple times, we only add the root node once to our result.

Solution Approach

The solution uses a Depth-First Search (DFS) traversal to visit each node in the binary tree. For each node, it constructs a unique string representation (serialization) of the subtree rooted at that node. This string representation encodes the structure and node values of the subtree. A hash table (`memo`) is used to store these string representations and assign unique IDs to each. A second hash table (`counts`) tracks how many times each unique ID has been encountered. If a subtree's ID appears twice in the `counts` table, it means we've found a duplicate, and we add the root of that subtree to our result list. The DFS function returns a unique ID for each subtree, allowing the parent node to construct its own subtree representation.

Step-by-Step Algorithm

Step 1: Initialize data structures: `memo` (hash table to store subtree strings and IDs), `counts` (hash table to count the occurrences of each ID), `res` (list to store the root nodes of duplicate subtrees), and `current_id` (unique ID counter).
Step 2: Define a recursive DFS function that takes a node as input.
Step 3: Base case: If the node is `None` (empty), return a special ID (e.g., 0) indicating an empty subtree.
Step 4: Recursively call DFS on the left and right children of the current node to get their respective IDs.
Step 5: Construct a string representation (subtree_key) of the current subtree using the node's value and the IDs of its left and right subtrees. The representation should uniquely identify the subtree's structure and values (e.g., `node.val + ',' + left_id + ',' + right_id`).
Step 6: Check if the subtree_key is already present in `memo`. If not, assign a new unique `current_id` to it and store it in `memo`.
Step 7: Increment the count of the subtree's ID in the `counts` table.
Step 8: If the count of the subtree's ID in `counts` is equal to 2, it means we've found a duplicate of this subtree, so append the current node to the `res` list. Note: We only add the node the first time we see the *second* instance.
Step 9: Return the ID of the current subtree from the DFS function. This ID will be used by the parent node to construct its own subtree representation.
Step 10: Call the DFS function on the root of the tree.
Step 11: Return the `res` list containing the root nodes of the duplicate subtrees.

Key Insights

Insight 1: We need a way to uniquely identify each subtree's structure and values. This is crucial for comparing subtrees to detect duplicates.
Insight 2: Serializing the subtree into a string allows us to use a hash table (dictionary) to efficiently track the occurrence of each unique subtree structure.
Insight 3: Using a unique ID for each subtree streamlines the counting process, avoiding string comparisons for every duplicate check.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Hash Table, Tree, Depth-First Search, Binary Tree.

Companies

Asked at: PhonePe, Yandex.

Find Duplicate Subtrees | LeetCode 652

Medium

Hash Table Tree Depth-First Search Binary Tree

Time: O(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;
 *     }
 * }
 */
import java.util.*;

class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    private Map<Integer, Integer> counts = new HashMap<>();
    private List<TreeNode> res = new ArrayList<>();
    private int current_id = 1;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left_id = dfs(node.left);
        int right_id = dfs(node.right);

        String subtree_key = node.val + "," + left_id + "," + right_id;

        if (!memo.containsKey(subtree_key)) {
            memo.put(subtree_key, current_id++);
        }

        int uid = memo.get(subtree_key);

        counts.put(uid, counts.getOrDefault(uid, 0) + 1);

        if (counts.get(uid) == 2) {
            res.add(node);
        }

        return uid;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 652: Find Duplicate Subtrees - Detailed explanation and solution approaches.

Topics

Hash Table Tree Depth-First Search Binary Tree

Companies

PhonePeYandex

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:652

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

11 steps

1
Step 1: Initialize data structures: `memo` (hash table to store subtree strings and IDs), `counts` (hash table to count the occurrences of each ID), `res` (list to store the root nodes of duplicate subtrees), and `current_id` (unique ID counter).
2
Step 2: Define a recursive DFS function that takes a node as input.
3
Step 3: Base case: If the node is `None` (empty), return a special ID (e.g., 0) indicating an empty subtree.
4
Step 4: Recursively call DFS on the left and right children of the current node to get their respective IDs.
5
Step 5: Construct a string representation (subtree_key) of the current subtree using the node's value and the IDs of its left and right subtrees. The representation should uniquely identify the subtree's structure and values (e.g., `node.val + ',' + left_id + ',' + right_id`).
6
Step 6: Check if the subtree_key is already present in `memo`. If not, assign a new unique `current_id` to it and store it in `memo`.
7
Step 7: Increment the count of the subtree's ID in the `counts` table.
8
Step 8: If the count of the subtree's ID in `counts` is equal to 2, it means we've found a duplicate of this subtree, so append the current node to the `res` list. Note: We only add the node the first time we see the *second* instance.
9
Step 9: Return the ID of the current subtree from the DFS function. This ID will be used by the parent node to construct its own subtree representation.
10
Step 10: Call the DFS function on the root of the tree.
11
Step 11: Return the `res` list containing the root nodes of the duplicate subtrees.

💡

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(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The DFS traversal visits each node once, performing constant-time operations (string concatenation, hash table lookups) at each node. Therefore, the time complexity is directly proportional to the number of nodes, O(n). The space complexity is determined by the size of the hash tables (`memo` and `counts`) and the depth of the recursion stack. In the worst case, these can all be proportional to the number of nodes, leading to a space complexity of O(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

Serialization with Postorder Traversal and String Comparison

Serialize each subtree using a postorder traversal and store the string representation in a set. For each new subtree, compare its serialized string with all the strings in the set. If a match is found, it's a duplicate.

Time: O(n^2) in the worst case (due to string comparisons), but can be closer to O(n*m) on average, where m is the average string length.Space: O(n), to store the serialized strings.

Trade-offs: Easier to understand initially, but less efficient than the hash table approach due to the cost of string comparisons. It's viable for smaller trees but becomes slow for larger ones.

✨

Key Insights

1Insight 1: We need a way to uniquely identify each subtree's structure and values. This is crucial for comparing subtrees to detect duplicates.
2Insight 2: Serializing the subtree into a string allows us to use a hash table (dictionary) to efficiently track the occurrence of each unique subtree structure.
3Insight 3: Using a unique ID for each subtree streamlines the counting process, avoiding string comparisons for every duplicate check.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is None). The code handles this correctly because the DFS function immediately returns 0, and no further processing occurs.
Edge case 2: A tree with only one node. The DFS will return a representation for this single node, and its count will be 1. No duplicates will be found, so the result list will be empty, which is the expected behavior.
Edge case 3: A tree where all the nodes are same value and structure leads to quadratic behavior in C solution because of hash table collisions. Good hash function choice is paramount to avoid O(n^2) behavior.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not including the structure of the subtree in the string representation. Only considering node values will lead to incorrect identification of duplicate subtrees.

✗Common mistake 2: Failing to handle the base case (empty tree or leaf node) correctly in the recursive DFS function. This can lead to errors or infinite loops.

✗Common mistake 3: Incrementing the `current_id` counter even when the `subtree_key` is present in `memo`. The counter should only be incremented when a new unique subtree is encountered.

✅

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: Code optimization. Identifying duplicate code blocks in a large codebase can help developers refactor and reduce redundancy.

🏦Real-world scenario 2: Data compression. Identifying repeating patterns (similar to duplicate subtrees) in data can be used for lossless compression techniques.

💡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

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

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: September 21, 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

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

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.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

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 "Find Duplicate Subtrees"?

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

🤖 Need help with this problem?