Find Duplicate Subtrees (LeetCode 652)
The input is one binary tree, passed as its root. A subtree is a node together with all the nodes below it. Two subtrees are duplicates when they have the same shape and the same value at every position.
Some shapes appear more than once in the tree. Find every shape that appears at least twice. For each such shape, report the root of one of its copies, not the root of every copy.
Worked Examples
root = [1,2,3,4,null,2,4,null,null,4][[2,4],[4]][2, 4].root = [2,1,1][[1]][1].root = [2,2,2,3,null,3,null][[2,3],[3]][2, 3].⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 5000].-200 <= Node.val <= 200
Core Insight
Write each subtree as one string made of its value and the strings of its two children, with # for a missing child. Two subtrees are the same exactly when their strings are the same, so counting the strings finds every repeated shape in one pass.
Real-World Scenario & Production Applications
A tool that removes duplicate folders from a file system, or a compiler that stores each repeated piece of a syntax tree only once, must find the parts of a tree that are exactly the same. It writes each part as a short text key, and then it compares keys instead of comparing whole parts again and again.
Step-by-Step Execution Trace Table
Example 3, root = [2,2,2,3,null,3,null], one row for each node, in the order key_of finishes them. A missing child returns "#" and is not listed.
| Step | Node | key | seen[key] | repeated |
|---|---|---|---|---|
| 1 | the left leaf 3 | 3,#,# | 1 | [] |
| 2 | the left 2 | 2,3,#,#,# | 1 | [] |
| 3 | the right leaf 3 | 3,#,# | 2 | [3] |
| 4 | the right 2 | 2,3,#,#,# | 2 | [3, 2] |
| 5 | the root 2 | 2,2,3,#,#,#,2,3,#,#,# | 1 | [3, 2] |
| End | sorted(repeated) = [2, 3] |
At steps 3 and 4, the key was already in seen, so its count reached 2 and the root value was recorded once.
root = [1,2,3,4,null,2,4,null,null,4][[2,4],[4]]Example 3, root = [2,2,2,3,null,3,null], one row for each node, in the order key_of finishes them. A missing child returns "#" and is not listed.
| Step | Node | key | seen[key] | repeated |
|---|---|---|---|---|
| 1 | the left leaf 3 | 3,#,# | 1 | [] |
| 2 | the left 2 | 2,3,#,#,# | 1 | [] |
| 3 | the right leaf 3 | 3,#,# | 2 | [3] |
| 4 | the right 2 | 2,3,#,#,# | 2 | [3, 2] |
| 5 | the root 2 | 2,2,3,#,#,#,2,3,#,#,# | 1 | [3, 2] |
| End | sorted(repeated) = [2, 3] |
At steps 3 and 4, the key was already in seen, so its count reached 2 and the root value was recorded once.
| 1 | A subtree repeats when another subtree has the same shape and the same values, so give every subtree a string that is equal for equal subtrees: `key_of(node)`. |
| 2 | A key is built after both children return: `key = f"{node.val},{left_key},{right_key}"`, with `#` for a missing child. |
| 3 | Count the keys: `seen[key] = seen.get(key, 0) + 1`, and record the root value when `seen[key] == 2`. |
| 4 | The trap: leave nothing out of the key. Without the `#` for a missing child, a node with only a left child `2` and a node with only a right child `2` give the same text. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS lets every subtree hand its parent one finished answer. Some questions compare the subtrees of one tree with each other: which shapes appear twice, or whether one tree appears inside another. Comparing two subtrees directly means walking both of them every time. Tree as a String gives every subtree a name instead. key_of(node) returns a string built from node.val and the strings of its two children, so two subtrees have the same string exactly when they have the same shape and the same values. Then the subtrees are counted, grouped or compared by their strings.
🏢 The Analogy: Labels on Nested Boxes
Every box holds a number and two smaller boxes, and either of them can be empty. A clerk writes a label for each box: the number, then the label of the left box, then the label of the right box, with a # for an empty place. The clerk writes the label of a box only after both smaller boxes have labels. Two boxes with the same label hold the same contents, so the clerk finds the repeated boxes by counting labels.
🔑 Why It Works
key = f"{node.val},{left_key},{right_key}" always has the value first, the left key second and the right key third, so a position in the key always means one position in the tree. The # marks a missing child, so a node with only a left child and a node with only a right child get different keys. seen[key] counts each key, and if seen[key] == 2: records a shape once, at its second sighting.
Leaving a missing child out of the key
Joining the parts of the key without separators
Reporting a shape every time it is seen again
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Duplicate subtrees" with "the same structure with the same node values": the question compares the subtrees of one tree with each other, so each subtree needs a name that is equal for equal subtrees. That is the signal for Tree as a String: build a string for every subtree from the strings of its children.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
key_of(node) returns f"{node.val},{left_key},{right_key}", with # for a missing child. Two subtrees have the same key exactly when they have the same shape and the same values. seen[key] counts the subtrees with each key, and repeated gets a root value when seen[key] == 2.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: a key must keep a
#for every missing child. A key that skips the missing child gives1,2to a node with only a left child2and to a node with only a right child2. On[0,1,1,2,null,null,2]the answer must be[2], not[1, 2].Join the parts with commas: without them, a node
1over a left child11and a node11over a left child1both give111###. On[0,1,11,11,null,1]the answer must be[].Record a shape when
seen[key] == 2, notseen[key] >= 2: on[1,2,2,3,3,3,3]the leaf shape3appears four times and must be reported once.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree as a String. The question compares subtrees of one tree with each other, so every subtree needs a name that is the same for equal subtrees. I write key of node. It asks the left child and the right child for their keys first, and then it joins the node's value with those two keys, with commas between them, into one string. A missing child returns a hash mark, so every key has a place for both children. Then two subtrees have the same key exactly when they have the same shape and the same values. I count each key in a dictionary, and when a count reaches two I record the root value, so each repeated shape is reported once. Every key is as long as its subtree, so on a chain the time and space are O of N squared. The trap I avoid is leaving out the hash mark for a missing child, which makes a left child and a right child look the same.
Complexity & Mathematical Proof
O(N^2)
Look at the code: key_of is called once for each node and once for each missing child, so there are at most 2 * N + 1 calls. Building key copies the two child keys, and a key is as long as its subtree, so a node with s nodes in its subtree costs O(s). Reading key to update seen costs O(s) too. The sizes of all subtrees add up to at most N * (N + 1) / 2, which happens on a chain, so the total is O(N^2). On a balanced tree the sizes add up to O(N log N).
O(N^2)
seen stores one key for each different shape. The longest keys are as long as the whole tree, so on a chain the keys add up to O(N^2) characters. The recursion goes one level deeper for each level of the tree: O(H) frames. repeated holds at most N values.
Derivation Progression
at most 2N + 1
One call for each node and one call for each missing child.
O(size(v))
Joining the value with the two child keys copies the whole key, and reading it for seen costs the same.
O(N^2)
The subtree sizes add up to N(N+1)/2 on a chain, and to O(N log N) on a balanced tree.
Variable Definitions
Number of nodes in the tree
Number of nodes in the subtree of node v, which is also the length of its key up to the length of one value
Height of the tree: the recursion never goes deeper
Memory Architecture & Bounds
O(H): one frame for each level of the path from the root to the current node
O(N^2): seen stores a key for each different shape, and the keys add up to O(N^2) characters on a chain
O(N): repeated holds at most N values
Boundary Best / Worst Cases
on a balanced tree: the subtree sizes add up to .
Between and : the cost is the sum of the subtree sizes, which grows with the height of the tree.
time and space on a chain, where the subtree sizes are .
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "duplicate subtrees", "the same structure with the same node values". Subtrees of one tree compared with each other: Tree as a String, where every subtree gets a key that is equal for equal subtrees.
nodes and values in . Comparing every pair of subtrees node by node is up to pairs of work each. One bottom-up pass does calls, and each key is as long as its subtree, so the keys add up to characters on a chain.
A recursive walk on a chain of 5000 nodes is 5000 calls deep, past CPython's default recursion limit of 1000: raise the limit or use an explicit stack. Every key keeps a # for a missing child and a comma between the parts. Without them, 1,2 stands for both a left child and a right child, and 111### stands for both 1 over 11 and 11 over 1.
Find Duplicate Subtrees (LeetCode 652)
The input is one binary tree, passed as its root. A subtree is a node together with all the nodes below it. Two subtrees are duplicates when they have the same shape and the same value at every position.
Some shapes appear more than once in the tree. Find every shape that appears at least twice. For each such shape, report the root of one of its copies, not the root of every copy.
Worked Examples
root = [1,2,3,4,null,2,4,null,null,4][[2,4],[4]][2, 4].root = [2,1,1][[1]][1].root = [2,2,2,3,null,3,null][[2,3],[3]][2, 3].⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 5000].-200 <= Node.val <= 200
Core Insight
Write each subtree as one string made of its value and the strings of its two children, with # for a missing child. Two subtrees are the same exactly when their strings are the same, so counting the strings finds every repeated shape in one pass.
Real-World Scenario & Production Applications
A tool that removes duplicate folders from a file system, or a compiler that stores each repeated piece of a syntax tree only once, must find the parts of a tree that are exactly the same. It writes each part as a short text key, and then it compares keys instead of comparing whole parts again and again.
Step-by-Step Execution Trace Table
Example 3, root = [2,2,2,3,null,3,null], one row for each node, in the order key_of finishes them. A missing child returns "#" and is not listed.
| Step | Node | key | seen[key] | repeated |
|---|---|---|---|---|
| 1 | the left leaf 3 | 3,#,# | 1 | [] |
| 2 | the left 2 | 2,3,#,#,# | 1 | [] |
| 3 | the right leaf 3 | 3,#,# | 2 | [3] |
| 4 | the right 2 | 2,3,#,#,# | 2 | [3, 2] |
| 5 | the root 2 | 2,2,3,#,#,#,2,3,#,#,# | 1 | [3, 2] |
| End | sorted(repeated) = [2, 3] |
At steps 3 and 4, the key was already in seen, so its count reached 2 and the root value was recorded once.
root = [1,2,3,4,null,2,4,null,null,4][[2,4],[4]]Example 3, root = [2,2,2,3,null,3,null], one row for each node, in the order key_of finishes them. A missing child returns "#" and is not listed.
| Step | Node | key | seen[key] | repeated |
|---|---|---|---|---|
| 1 | the left leaf 3 | 3,#,# | 1 | [] |
| 2 | the left 2 | 2,3,#,#,# | 1 | [] |
| 3 | the right leaf 3 | 3,#,# | 2 | [3] |
| 4 | the right 2 | 2,3,#,#,# | 2 | [3, 2] |
| 5 | the root 2 | 2,2,3,#,#,#,2,3,#,#,# | 1 | [3, 2] |
| End | sorted(repeated) = [2, 3] |
At steps 3 and 4, the key was already in seen, so its count reached 2 and the root value was recorded once.
| 1 | A subtree repeats when another subtree has the same shape and the same values, so give every subtree a string that is equal for equal subtrees: `key_of(node)`. |
| 2 | A key is built after both children return: `key = f"{node.val},{left_key},{right_key}"`, with `#` for a missing child. |
| 3 | Count the keys: `seen[key] = seen.get(key, 0) + 1`, and record the root value when `seen[key] == 2`. |
| 4 | The trap: leave nothing out of the key. Without the `#` for a missing child, a node with only a left child `2` and a node with only a right child `2` give the same text. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS lets every subtree hand its parent one finished answer. Some questions compare the subtrees of one tree with each other: which shapes appear twice, or whether one tree appears inside another. Comparing two subtrees directly means walking both of them every time. Tree as a String gives every subtree a name instead. key_of(node) returns a string built from node.val and the strings of its two children, so two subtrees have the same string exactly when they have the same shape and the same values. Then the subtrees are counted, grouped or compared by their strings.
🏢 The Analogy: Labels on Nested Boxes
Every box holds a number and two smaller boxes, and either of them can be empty. A clerk writes a label for each box: the number, then the label of the left box, then the label of the right box, with a # for an empty place. The clerk writes the label of a box only after both smaller boxes have labels. Two boxes with the same label hold the same contents, so the clerk finds the repeated boxes by counting labels.
🔑 Why It Works
key = f"{node.val},{left_key},{right_key}" always has the value first, the left key second and the right key third, so a position in the key always means one position in the tree. The # marks a missing child, so a node with only a left child and a node with only a right child get different keys. seen[key] counts each key, and if seen[key] == 2: records a shape once, at its second sighting.
Leaving a missing child out of the key
Joining the parts of the key without separators
Reporting a shape every time it is seen again
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Duplicate subtrees" with "the same structure with the same node values": the question compares the subtrees of one tree with each other, so each subtree needs a name that is equal for equal subtrees. That is the signal for Tree as a String: build a string for every subtree from the strings of its children.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
key_of(node) returns f"{node.val},{left_key},{right_key}", with # for a missing child. Two subtrees have the same key exactly when they have the same shape and the same values. seen[key] counts the subtrees with each key, and repeated gets a root value when seen[key] == 2.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: a key must keep a
#for every missing child. A key that skips the missing child gives1,2to a node with only a left child2and to a node with only a right child2. On[0,1,1,2,null,null,2]the answer must be[2], not[1, 2].Join the parts with commas: without them, a node
1over a left child11and a node11over a left child1both give111###. On[0,1,11,11,null,1]the answer must be[].Record a shape when
seen[key] == 2, notseen[key] >= 2: on[1,2,2,3,3,3,3]the leaf shape3appears four times and must be reported once.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree as a String. The question compares subtrees of one tree with each other, so every subtree needs a name that is the same for equal subtrees. I write key of node. It asks the left child and the right child for their keys first, and then it joins the node's value with those two keys, with commas between them, into one string. A missing child returns a hash mark, so every key has a place for both children. Then two subtrees have the same key exactly when they have the same shape and the same values. I count each key in a dictionary, and when a count reaches two I record the root value, so each repeated shape is reported once. Every key is as long as its subtree, so on a chain the time and space are O of N squared. The trap I avoid is leaving out the hash mark for a missing child, which makes a left child and a right child look the same.
Complexity & Mathematical Proof
O(N^2)
Look at the code: key_of is called once for each node and once for each missing child, so there are at most 2 * N + 1 calls. Building key copies the two child keys, and a key is as long as its subtree, so a node with s nodes in its subtree costs O(s). Reading key to update seen costs O(s) too. The sizes of all subtrees add up to at most N * (N + 1) / 2, which happens on a chain, so the total is O(N^2). On a balanced tree the sizes add up to O(N log N).
O(N^2)
seen stores one key for each different shape. The longest keys are as long as the whole tree, so on a chain the keys add up to O(N^2) characters. The recursion goes one level deeper for each level of the tree: O(H) frames. repeated holds at most N values.
Derivation Progression
at most 2N + 1
One call for each node and one call for each missing child.
O(size(v))
Joining the value with the two child keys copies the whole key, and reading it for seen costs the same.
O(N^2)
The subtree sizes add up to N(N+1)/2 on a chain, and to O(N log N) on a balanced tree.
Variable Definitions
Number of nodes in the tree
Number of nodes in the subtree of node v, which is also the length of its key up to the length of one value
Height of the tree: the recursion never goes deeper
Memory Architecture & Bounds
O(H): one frame for each level of the path from the root to the current node
O(N^2): seen stores a key for each different shape, and the keys add up to O(N^2) characters on a chain
O(N): repeated holds at most N values
Boundary Best / Worst Cases
on a balanced tree: the subtree sizes add up to .
Between and : the cost is the sum of the subtree sizes, which grows with the height of the tree.
time and space on a chain, where the subtree sizes are .
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "duplicate subtrees", "the same structure with the same node values". Subtrees of one tree compared with each other: Tree as a String, where every subtree gets a key that is equal for equal subtrees.
nodes and values in . Comparing every pair of subtrees node by node is up to pairs of work each. One bottom-up pass does calls, and each key is as long as its subtree, so the keys add up to characters on a chain.
A recursive walk on a chain of 5000 nodes is 5000 calls deep, past CPython's default recursion limit of 1000: raise the limit or use an explicit stack. Every key keeps a # for a missing child and a comma between the parts. Without them, 1,2 stands for both a left child and a right child, and 111### stands for both 1 over 11 and 11 over 1.