Find All Duplicate Subtrees in a Binary Tree

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.

Find All Duplicate Subtrees in a Binary Tree - Code Examples 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)