Leetcode 652. Find Duplicate Subtrees

Question

The question is of finding duplicate subtrees and the approach used is to convert each subtree to a post order tree and compare them.

class Solution {
public:
    vector<TreeNode*> ans;
    unordered_map<string, int> list;
    string helper(TreeNode* root){
        if(!root)return "";
        string cur = helper(root->left)+" "+helper(root->right)+" "+to_string(root->val);
        if(list[cur] == 1)ans.push_back(root);
        list[cur]++;
        return cur;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        helper(root);
        return ans;
    }
};

But when I try the same question with mid order traversal it wont work. can someone explain why is that?

I want to know why it is not working with mid order traversal and only with pre and post order strings.

Answer 1

Consider these two trees:

  2           1
 / \           \
1   3           2
                 \
                  3

The inorder traversal for both trees would be 1 -> 2 -> 3. Simply put, inorder traversal won't guarantee uniqueness. That's why your solution returns an incorrect answer.

Using preorder/postorder traversal does not guarantee uniqueness either. If you include "null" nodes in your traversal, then they'll give a unique string for each tree. But even then inorder traversal will not guarantee uniqueness.