Find All Duplicate Subtrees in a Binary Tree - Algorithm, Visualization, Examples

Problem Statement❯

Given the root of a binary tree, return all duplicate subtrees. For two trees to be considered duplicate, they must have the same structure and the same node values. You can return the root node of any one of the duplicate subtrees. Each duplicate subtree should be included only once in the result.

Examples❯

Input Tree	Duplicate Subtrees (Serialized)	Description
[1, 2, 3, 4, null, 2, 4, null, null, 4]	['4', '2,4,null,null,null']	The subtree rooted at value 4 appears three times. The subtree [2, 4] also appears twice.
[1, 2, 3, 4, null, 4, null, null, null, 4]	['4']	The leaf node with value 4 appears multiple times, forming duplicate subtrees.
[1, 2, 3]	[]	All subtrees are unique; no duplicate subtree structure exists.
[0, 0, 0, 0, null, null, 0]	['0']	The leaf node with value 0 appears three times. These are duplicate subtrees.
[2, 1, 1, null, null, null, 1]	['1']	There are multiple leaf nodes with value 1, which are considered duplicate subtrees.

Solution❯

Case 1: Normal Case (Duplicate subtrees exist)

Consider the binary tree: [1,2,3,4,null,2,4,null,null,4]. If you visualize it, you'll see that there are two subtrees with structure 4 and two with structure 2 → 4. In both cases, the values and structure match completely, so these are duplicate subtrees.

The approach to detect these is to serialize each subtree using post-order traversal into strings like 4,#,# for a leaf node with value 4. This serialization helps identify structural duplicates. Every time we see the same serialization again, we know we've found a duplicate. We return only one instance of the duplicate subtree root.

Case 2: Edge Case (All subtrees are unique)

Now consider a tree like [1,2,3]. The tree is small, and all subtrees (rooted at 1, 2, and 3) are distinct. When we serialize each subtree, no two serializations match. Hence, the output is an empty list [], indicating there are no duplicates. This is a common edge case where the tree is small and diverse in structure.

Case 3: Empty Tree

For an input like [], the tree doesn't exist at all. Since there are no nodes, the question of duplicate subtrees doesn’t arise. The output is naturally an empty list []. This represents the base case and should be checked before processing the tree to avoid null pointer errors.

Algorithm Steps❯

Perform a postorder traversal of the binary tree.
For each node, generate a unique serialization string representing the subtree rooted at that node. Use a format like node.val,left_serial,right_serial.
Use a hash map (or dictionary) to count the occurrences of each serialized subtree.
If a serialization appears more than once, add the subtree's root to the result list (ensuring each duplicate is added only once).
Return the list of duplicate subtree roots.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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) -> list:
        count = {}
        result = []
        
        def traverse(node):
            if not node:
                return '#'
            serial = f'{node.val},' + traverse(node.left) + ',' + traverse(node.right)
            count[serial] = count.get(serial, 0) + 1
            if count[serial] == 2:
                result.append(node)
            return serial
        
        traverse(root)
        return result

# Example usage:
if __name__ == '__main__':
    # Construct binary tree sample
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   2   4
    #        /
    #       4
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
    sol = Solution()
    duplicates = sol.findDuplicateSubtrees(root)
    for node in duplicates:
        print(node.val)

⬅ Previous TopicFind the kth Ancestor of a Node in a Binary Tree

Next Topic ⮕Find a Value in a Binary Search Tree