DSA problem
Find Duplicate Subtrees
Given the root of a binary tree, return all duplicate subtrees. For each kind of duplicate subtree, 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.
The natural approach is to assign each subtree a canonical serialization — a string that uniquely identifies its shape and values. A clean format is "val,leftSerial,rightSerial" with "#" for nulls; equivalent subtrees produce identical strings, distinct subtrees produce distinct strings.
This is computed in a single post-order traversal. Each node first recursively obtains the serializations of its left and right children, then concatenates them with its own value to form its own serialization. We maintain a hash map from serialization to count; the first time we see a serialization more than once, we record the current node as a representative of that duplicate class.
The subtlety is performance. Naive string concatenation gives a worst-case quadratic blowup (each level's serialization is roughly the size of the whole subtree). For the constraints given (≤ 10⁴ nodes, values within ±200), the naive O(n²) is acceptable. An asymptotically better solution interns each serialization into a unique integer ID (a fresh ID per unseen tuple (val, leftId, rightId)) and works in O(n) time and O(n) space.
Examples
root = [1,2,3,4,null,2,4,null,null,4][[2,4],[4]]root = [2,1,1][[1]]root = [2,2,2,3,null,3,null][[2,3],[3]]Constraints
- The number of the nodes in the tree will be in the range [1, 10^4].
- -200 <= Node.val <= 200
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.