Find-All-Duplicate-Subtrees.py

# Python3 program to find averages of
# all levels in a binary tree.

# Helper function that allocates a
# new node with the given data and
# None left and right pointers.
classnewNode:
def__init__(self, data):
self.data=data
self.left=self.right=None

definorder(node, m):
if (notnode):
return""

Str="("
Str+=inorder(node.left, m)
Str+=str(node.data)
Str+=inorder(node.right, m)
Str+=")"

# Subtree already present (Note that
# we use unordered_map instead of
# unordered_set because we want to print
# multiple duplicates only once, consider
# example of 4 in above subtree, it
# should be printed only once.
if (Strinmandm[Str] ==1):
print(node.data, end=" ")
ifStrinm:
m[Str] +=1
else:
m[Str] =1

returnStr

# Wrapper over inorder()
defprintAllDups(root):
m= {}
inorder(root, m)

# Driver code
if__name__=='__main__':
root=None
root=newNode(1)
root.left=newNode(2)
root.right=newNode(3)
root.left.left=newNode(4)
root.right.left=newNode(2)
root.right.left.left=newNode(4)
root.right.right=newNode(4)
printAllDups(root)