Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More

Algorithm Steps

Traverse the binary tree in a postorder manner and serialize each subtree into a string representation.
For each node, if the node is not a leaf (i.e. it has at least one child), store its serialized string in a hash map with a frequency count.
If the frequency of any serialized subtree becomes 2 (or more), mark that duplicate has been found.
After processing all nodes, if a duplicate subtree (of size 2 or more) is detected, return true; otherwise, return false.

Check for Duplicate Subtrees of Size 2 or More - 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


def hasDuplicateSubtrees(root):
    seen = {}
    duplicate = False

    def serialize(node):
        nonlocal duplicate
        if not node:
            return '#'
        left = serialize(node.left)
        right = serialize(node.right)
        subtree = str(node.val) + ',' + left + ',' + right
        # Only consider subtrees of size >= 2 (node with at least one child)
        if node.left or node.right:
            seen[subtree] = seen.get(subtree, 0) + 1
            if seen[subtree] == 2:
                duplicate = True
        return subtree

    serialize(root)
    return duplicate

# Example usage:
if __name__ == '__main__':
    # Construct a sample binary tree:
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   2   4
    #        /
    #       4
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
    print(hasDuplicateSubtrees(root))