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

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)