Check if a Binary Tree contains duplicate subtrees of size 2 or more | Python3 program to find if there is a duplicate sub - tree of size 2 or more Separator node ; Structure for a binary tree node ; This function returns empty if tree contains a duplicate subtree of size 2 or more . ; If current node is None , return marker ; If left subtree has a duplicate subtree . ; Do same for right subtree ; Serialize current subtree ; If current subtree already exists in hash table . [ Note that size of a serialized tree with single node is 3 as it has two marker nodes . ; Driver code
MARKER = ' $ ' NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . key = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT subtrees = { } NEW_LINE def dupSubUtil ( root ) : NEW_LINE INDENT global subtrees NEW_LINE s = " " NEW_LINE if ( root == None ) : NEW_LINE INDENT return s + MARKER NEW_LINE DEDENT lStr = dupSubUtil ( root . left ) NEW_LINE if ( s in lStr ) : NEW_LINE return s NEW_LINE rStr = dupSubUtil ( root . right ) NEW_LINE if ( s in rStr ) : NEW_LINE return s NEW_LINE s = s + root . key + lStr + rStr NEW_LINE if ( len ( s ) > 3 and s in subtrees ) : NEW_LINE return " " NEW_LINE subtrees [ s ] = 1 NEW_LINE return s NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( ' A ' ) NEW_LINE root . left = Node ( ' B ' ) NEW_LINE root . right = Node ( ' C ' ) NEW_LINE root . left . left = Node ( ' D ' ) NEW_LINE root . left . right = Node ( ' E ' ) NEW_LINE root . right . right = Node ( ' B ' ) NEW_LINE root . right . right . right = Node ( ' E ' ) NEW_LINE root . right . right . left = Node ( ' D ' ) NEW_LINE str = dupSubUtil ( root ) NEW_LINE if " " in str : NEW_LINE INDENT print ( " ▁ Yes ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " ▁ No ▁ " ) NEW_LINE DEDENT DEDENT