Find Duplicate Subtrees

Find Duplicate Subtrees is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Serialization and Deserialization subpattern.

Problem statement

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

Topics and companies

Topics: Hash Table, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Google, Amazon.

How to practise Find Duplicate Subtrees on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of nodes in the tree. Each node is visited once, and all operations (hashing, map lookups) are O(1) amortized. time and O(n), for the hash maps storing subtree serializations and counts, and for the recursion stack in the worst case. space.

Open Find Duplicate Subtrees in the code editor, or read the Find Duplicate Subtrees editorial for a worked solution with its approach and complexity analysis.

Where Find Duplicate Subtrees sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Serialization and Deserialization subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find Duplicate Subtrees

Other problems that use the same Serialization and Deserialization and Tree Traversal Patterns (DFS & BFS) techniques:

• Serialize and Deserialize Binary Tree — Hard, same subpattern
• Subtree of Another Tree — Easy, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern
• Balanced Binary Tree — Easy, same pattern
• Binary Search Tree Iterator — Medium, same pattern
• Binary Tree Inorder Traversal — Easy, same pattern