Find Duplicate Subtrees
Medium · Trees · Hash Table · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, find every kind of subtree that appears more than once. Two subtrees are the same kind when they have the same shape and the same value in every position.
For each kind that repeats, return the root node of one of its occurrences (a node of the input tree). The list may be in any order.
The tree is written as a level-order list with None for a missing child. The grader checks that every returned node belongs to the input tree, then compares the level-order lists of the returned subtrees, in any order.
Examples
Input: root = [1,2,3,4,None,2,None,None,None,4] Output: [[4],[2,4]]
The subtree 2 with a left child 4 appears under the root and under 3. The single leaf 4 appears twice as well.
Input: root = [7,3,3] Output: [[3]]
The two leaves holding 3 are identical.
Input: root = [2,1,1,3,None,None,3] Output: [[3]]
Both 1 nodes have a child 3, but one on the left and one on the right: different shapes. Only the leaf 3 repeats.
Constraints
- 1 <= number of nodes <= 5000
- -200 <= Node.val <= 200
Approaches
- Serialize every subtree from scratch — time O(n²), space O(n²)
Follow-up
Serialization strings cost O(n²) because each parent copies its children's text. Hashing the triple without interning (a rolling or Merkle-style hash) is also O(n), but then two different subtrees can collide; the integer ids cannot.
Related problems
Start free on Cariara · Coding problems · System design studio
