algoadvance

Leetcode 652. Find Duplicate Subtrees

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.

Clarifying Questions:

  1. What is the definition of a subtree?
    • A subtree is a tree consisting of a node in a tree and all of its descendants.
  2. What should be returned if no duplicate subtrees are found?
    • Return an empty vector.
  3. Are the node values unique or can there be duplicates?
    • Node values can have duplicates, but we are looking for subtrees that are structurally identical with identical node values.

Strategy:

  1. Serialization of Subtrees: We need a way to uniquely identify a subtree. We can do this by serializing each subtree into a string format.
  2. Usage of Hash Map: Use a hash map to keep track of the count of each serialized subtree.
  3. Identify Duplicates: When a subtree is encountered more than once (count exceeds 1), it indicates a duplicate subtree.
  4. Record Roots: Record the root nodes of these duplicate subtrees.

Steps:

  1. Define a helper function to serialize a subtree.
  2. Traverse the tree using Depth-First Search (DFS), serialize each subtree, and record its occurrences.
  3. Collect the root nodes of subtrees that have duplicates.

Code:

#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>

// 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:
    std::vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        std::unordered_map<std::string, int> count;
        std::vector<TreeNode*> result;
        serialize(root, count, result);
        return result;
    }
    
private:
    std::string serialize(TreeNode* node, std::unordered_map<std::string, int>& count, std::vector<TreeNode*>& result) {
        if (!node)
            return "#"; // Use "#" to represent a null node.
        
        // Create a unique serialization for the subtree rooted at `node`.
        std::string serial = std::to_string(node->val) + "," +
                             serialize(node->left, count, result) + "," +
                             serialize(node->right, count, result);
        
        if (count[serial] == 1)
            result.push_back(node);

        count[serial]++;
        
        return serial;
    }
};

// Helper function to print the tree nodes (for verification purposes)
void printTreeNodeVector(const std::vector<TreeNode*>& nodes) {
    for (TreeNode* node : nodes) {
        std::cout << node->val << " ";
    }
    std::cout << std::endl;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(2);
    root->right->left->left = new TreeNode(4);
    root->right->right = new TreeNode(4);

    Solution solution;
    std::vector<TreeNode*> duplicates = solution.findDuplicateSubtrees(root);
    
    printTreeNodeVector(duplicates);
    
    return 0;
}

Time Complexity:

By following this strategy, we can efficiently find all duplicate subtrees within the given binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI