Find Duplicate Subtrees - Solution & Explanation

Problem Overview: You are given the root of a binary tree and need to return the roots of all subtrees that appear more than once. Two subtrees are considered duplicates if they have the same structure and the same node values. The challenge is efficiently detecting identical subtree structures across the entire tree.

Approach 1: Tree Serialization Using DFS (O(n²) time, O(n) space)

This approach converts every subtree into a unique string representation using postorder traversal. During a DFS traversal, you serialize the left subtree, the right subtree, and the current node value into a string like "left,right,val". A hash table tracks how many times each serialized subtree appears. When a serialization is seen for the second time, you record that subtree root as a duplicate.

The key insight is that identical subtree structures generate identical serialized strings. Using depth-first search, every node contributes to exactly one serialization result, allowing you to systematically compare subtrees without pairwise comparisons. The downside is that repeated string concatenation can grow large for deep trees, leading to a worst‑case time complexity of O(n²).

Approach 2: Tree Serialization with Unique Identifiers (O(n) time, O(n) space)

A more efficient strategy replaces full string serialization with compact integer identifiers. During DFS, each subtree is represented by a tuple containing the current node value and the IDs of its left and right subtrees. This tuple is stored in a hash map that assigns a unique integer ID the first time the structure appears.

Each subtree is therefore represented by a small numeric signature instead of a long string. Another map counts how many times each subtree ID appears, and once the count reaches two, the subtree root is added to the result list. Because each node is processed once and tuple lookups are constant time, the algorithm runs in O(n) time and uses O(n) space.

This approach works particularly well for large binary tree inputs because subtree comparisons become integer comparisons instead of string comparisons.

Recommended for interviews: The unique identifier approach is the one interviewers typically expect. It demonstrates strong understanding of DFS traversal, hashing, and subtree memoization while achieving optimal O(n) complexity. Explaining the basic serialization idea first shows clear reasoning, but optimizing it with subtree IDs highlights deeper algorithmic thinking.