Find Duplicate Subtrees solution and explanation
Google
9 more videos on this problem
Find Duplicate Subtrees - Leetcode 652 - PythonNeetCodeIO · 14:33 · 27K views
Find Duplicate Subtrees (Leetcode - 652) - (GOOGLE) : Explanation ➕ Live CodingcodestorywithMIK · 14:11 · 18K views
[Java] Leetcode 652. Find Duplicate Subtrees [Binary Tree #10]Eric Programming · 16:41 · 8K views
Find Duplicate Subtrees | Leetcode 652 | Binary TreesAyushi Sharma · 22:24 · 7K views
FIND DUPLICATE SUBTREES | LEETCODE # 652 | PYTHON DFS SOLUTIONCracking FAANG · 9:50 · 5K views
652. Find Duplicate Subtrees | English | MediumSimple Code - 단순코드 · 6:36 · 2K views
652. Find Duplicate Subtrees | LeetCode Medium | LeetCode Problem of the Day | LeetCode POTDDeep Tech · 15:38 · 1K views
Find Duplicate Subtrees (Medium) | Tree | Top 52 Uber LeetCode Premium Coding QuestionsAakash Verma · 18:19 · 656 views
Find Duplicate Subtrees - Leetcode 652 - PythonTechError · 15:26 · 590 views
Daily Leetcode #1064: Feb 28, 2023 - 652. Find Duplicate SubtreesProgramming Live with Larry · 47:18 · 448 views
The problem
Given the root of a binary tree, return all duplicate subtrees.
For each kind of duplicate subtrees, 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.
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]]
Example 2:
Input: root = [2,1,1] Output: [[1]]
Example 3:
Input: root = [2,2,2,3,null,3,null] Output: [[2,3],[3]]
Constraints:
- The number of the nodes in the tree will be in the range
[1, 5000] -200 <= Node.val <= 200
Approach overview
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(n2) 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(n2).
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.
Approach 1: Tree Serialization Using DFS
Utilize a Depth-First Search (DFS) strategy and serialize each subtree. Treat the serialization as a key in a hashmap to track occurrences of identical subtrees. Duplicate entries are detected when a serialized key is encountered more than once.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findDuplicateSubtrees(self, root: TreeNode):
from collections import defaultdict
def serialize(node):
if not node:
return '#'
serial = f'{node.val},{serialize(node.left)},{serialize(node.right)}'
count[serial].append(node)
return serial
count = defaultdict(list)
serialize(root)
return [nodes[0] for nodes in count.values() if len(nodes) > 1]import java.util.*;
public class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
Map<String, List<TreeNode>> map = new HashMap<>();
serialize(root, map);
List<TreeNode> result = new ArrayList<>();
for (List<TreeNode> nodes : map.values()) {
if (nodes.size() > 1) {
result.add(nodes.get(0));
}
}
return result;
}
private String serialize(TreeNode node, Map<String, List<TreeNode>> map) {
if (node == null) {
return "#";
}
String serial = node.val + "," + serialize(node.left, map) + "," + serialize(node.right, map);
map.computeIfAbsent(serial, k -> new ArrayList<>()).add(node);
return serial;
}
}#include <unordered_map>
#include <vector>
#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, vector<TreeNode*>> map;
serialize(root, map);
vector<TreeNode*> result;
for (auto& pair : map) {
if (pair.second.size() > 1) {
result.push_back(pair.second.front());
}
}
return result;
}
private:
string serialize(TreeNode* node, unordered_map<string, vector<TreeNode*>>& map) {
if (!node) return "#";
string serial = to_string(node->val) + "," + serialize(node->left, map) + "," + serialize(node->right, map);
map[serial].push_back(node);
return serial;
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var findDuplicateSubtrees = function(root) {
const map = new Map();
function serialize(node) {
if (!node) return '#';
const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
if (!map.has(serial)) {
map.set(serial, []);
}
map.get(serial).push(node);
return serial;
}
serialize(root);
const result = [];
for (const nodes of map.values()) {
if (nodes.length > 1) {
result.push(nodes[0]);
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unordered_map>
#include <vector>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
char* serialize(struct TreeNode* node, std::unordered_map<std::string, std::vector<struct TreeNode*>>& map) {
if (!node) return "#";
char* left = serialize(node->left, map);
char* right = serialize(node->right, map);
std::string serial = std::to_string(node->val) + "," + std::string(left) + "," + std::string(right);
map[serial].push_back(node);
return strdup(serial.c_str());
}
std::vector<struct TreeNode*> findDuplicateSubtrees(struct TreeNode* root) {
std::unordered_map<std::string, std::vector<struct TreeNode*>> map;
serialize(root, map);
std::vector<struct TreeNode*> result;
for (auto& pair : map) {
if (pair.second.size() > 1) {
result.push_back(pair.second.front());
}
}
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
var map = new Dictionary<string, List<TreeNode>>();
Serialize(root, map);
var result = new List<TreeNode>();
foreach (var pair in map) {
if (pair.Value.Count > 1) {
result.Add(pair.Value[0]);
}
}
return result;
}
private string Serialize(TreeNode node, Dictionary<string, List<TreeNode>> map) {
if (node == null) {
return "#";
}
string serial = node.val + "," + Serialize(node.left, map) + "," + Serialize(node.right, map);
if (!map.ContainsKey(serial)) {
map[serial] = new List<TreeNode>();
}
map[serial].Add(node);
return serial;
}
}This Python solution uses DFS to serialize each subtree into a string. These strings are stored in a dictionary. If a string appears more than once, it indicates a duplicate subtree. The function returns one node from each set of duplicates.
Time Complexity: O(N), where N is the number of nodes since we visit each node once.
Space Complexity: O(N), accounting for the hashmap to store serialized trees and recursion stack space.
Approach 2: Tree Serialization with Unique Identifiers
Rather than using direct serialization strings, assign each unique subtree encountered a unique ID using a hash map. If a subtree's ID is seen again, it's a duplicate.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findDuplicateSubtrees(self, root: TreeNode):
from collections import defaultdict
def serialize(node):
if not node:
return 0 # Unique ID for null references
sid = (node.val, serialize(node.left), serialize(node.right))
uid = ids[sid]
count[uid].append(node)
return uid
count = defaultdict(list)
ids = defaultdict(lambda: len(ids) + 1)
serialize(root)
return [nodes[0] for nodes in count.values() if len(nodes) > 1]import java.util.*;
public class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
Map<String, Integer> ids = new HashMap<>();
Map<String, Integer> count = new HashMap<>();
List<TreeNode> result = new ArrayList<>();
serialize(root, ids, count, new int[]{1}, result);
return result;
}
private int serialize(TreeNode node, Map<String, Integer> ids, Map<String, Integer> count, int[] id, List<TreeNode> result) {
if (node == null) return 0;
String serial = node.val + "," + serialize(node.left, ids, count, id, result) + "," + serialize(node.right, ids, count, id, result);
int uid = ids.computeIfAbsent(serial, k -> id[0]++);
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2) result.add(node);
return uid;
}
}#include <unordered_map>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
unordered_map<string, int> ids;
unordered_map<string, int> count;
vector<TreeNode*> result;
int idCounter = 1;
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
serialize(root);
return result;
}
private:
int serialize(TreeNode* node) {
if (!node) return 0;
string serial = to_string(node->val) + ',' + to_string(serialize(node->left)) + ',' + to_string(serialize(node->right));
if (!ids.count(serial)) {
ids[serial] = idCounter++;
}
int id = ids[serial];
if (++count[serial] == 2) {
result.push_back(node);
}
return id;
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var findDuplicateSubtrees = function(root) {
const ids = new Map(), count = new Map();
const result = [];
let idCounter = 1;
function serialize(node) {
if (!node) return 0;
const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
if (!ids.has(serial)) {
ids.set(serial, idCounter++);
}
const id = ids.get(serial);
count.set(id, (count.get(id) || 0) + 1);
if (count.get(id) === 2) result.push(node);
return id;
}
serialize(root);
return result;
};This Python approach maps each subtree structure to a unique identifier, incrementally assigning IDs using a dictionary. Duplicates are recognized when the same ID appears multiple times.
Time Complexity: O(N), as we traverse each node.
Space Complexity: O(N), necessary for dictionaries and recursive processing space.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
const map = new Map<string, number>();
const res = [];
const dfs = (root: TreeNode | null) => {
if (root == null) {
return '#';
}
const { val, left, right } = root;
const s = `${val},${dfs(left)},${dfs(right)}`;
map.set(s, (map.get(s) ?? 0) + 1);
if (map.get(s) === 2) {
res.push(root);
}
return s;
};
dfs(root);
return res;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
var ans []*TreeNode
counter := make(map[string]int)
var dfs func(root *TreeNode) string
dfs = func(root *TreeNode) string {
if root == nil {
return "#"
}
v := strconv.Itoa(root.Val) + "," + dfs(root.Left) + "," + dfs(root.Right)
counter[v]++
if counter[v] == 2 {
ans = append(ans, root)
}
return v
}
dfs(root)
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
fn dfs(
root: &Option<Rc<RefCell<TreeNode>>>,
map: &mut HashMap<String, i32>,
res: &mut Vec<Option<Rc<RefCell<TreeNode>>>>,
) -> String {
if root.is_none() {
return String::from('#');
}
let s = {
let root = root.as_ref().unwrap().as_ref().borrow();
format!(
"{},{},{}",
root.val.to_string(),
Self::dfs(&root.left, map, res),
Self::dfs(&root.right, map, res)
)
};
*map.entry(s.clone()).or_insert(0) += 1;
if *map.get(&s).unwrap() == 2 {
res.push(root.clone());
}
return s;
}
pub fn find_duplicate_subtrees(
root: Option<Rc<RefCell<TreeNode>>>,
) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
let mut map = HashMap::new();
let mut res = Vec::new();
Self::dfs(&root, &mut map, &mut res);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Tree Serialization Using DFS | Time Complexity: O(N), where N is the number of nodes since we visit each node once. |
| Tree Serialization with Unique Identifiers | Time Complexity: O(N), as we traverse each node. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Tree Serialization Using DFS | O(n^2) | O(n) | Simple implementation when tree size is moderate and string serialization cost is acceptable |
| Serialization with Unique Subtree Identifiers | O(n) | O(n) | Optimal solution for interviews and large trees where repeated string comparisons are expensive |
Frequently asked questions
Is Find Duplicate Subtrees easy or hard?
Find Duplicate Subtrees is generally considered a medium-level problem. The challenge lies in recognizing that subtree structures must be uniquely represented and compared efficiently, typically using DFS traversal combined with hashing.
Find Duplicate Subtrees Python/Java solution
Python and Java implementations typically perform a postorder DFS and store subtree representations in a hash map. The optimized version assigns unique IDs to subtree structures, ensuring O(n) time complexity while keeping memory usage linear.
How to solve Find Duplicate Subtrees in O(n)?
Traverse the tree using postorder DFS and assign a unique ID to each distinct subtree structure. Store tuples (value, leftID, rightID) in a hash map that maps structures to IDs. Maintain a frequency map for each ID and record the subtree root when its count reaches two.
What is the best approach for Find Duplicate Subtrees?
The most efficient approach uses DFS with unique subtree identifiers stored in a hash map. Each subtree is represented by a tuple of (node value, left subtree ID, right subtree ID), which is mapped to a unique integer. This avoids expensive string comparisons and runs in O(n) time with O(n) space.
Is Find Duplicate Subtrees asked at Google/Amazon/Meta?
Find Duplicate Subtrees is a common binary tree hashing problem that has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of DFS traversal, subtree representation, and efficient hashing techniques for structural comparison.
What data structure is used in Find Duplicate Subtrees?
The solution relies on hash maps to store serialized subtree representations or subtree identifiers and their frequencies. Depth-first search recursion processes the binary tree, while the hash table allows constant-time lookup to detect duplicate subtree structures.
What is the time complexity of Find Duplicate Subtrees?
The optimized solution runs in O(n) time because each node in the binary tree is processed once during DFS. Hash map lookups and ID assignments are constant time on average. A simpler serialization approach may degrade to O(n^2) time due to repeated string concatenation.