Given a binary tree of size N, your task is to that find all duplicate subtrees from the given binary tree.
Note: Here's the Output of every Node printed in the Pre-Order tree traversal format. Arrange nodes in the answer array based on the lexicographically increasing order of their preorder traversal of subtree.
For Example: if we have 3 preorder traversal as {1,2,3},{1},{11,2,3} then your lexicographically increasing order is {1},{1,2,3},{11,2,3}, you are supposed to output the head of all these subtrees in the same order.
Example:
Input : 
Output : 2 4
         4
Explanation: Above Trees are two 
duplicate subtrees.i.e  and 
Therefore,you need to return above trees 
root in the form of a list.
Your Task:
You don't need to take input. Just complete the function printAllDups() that takes the root node as a parameter and returns an array of Node*, which contains all the duplicate subtree.
Constraints:
1<=T<=100
1<=N<=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data=val

        self.left=None

        self.right=None

'''



class Solution:

    def printAllDups(self,root):

        #code here

Solutions:
class Solution:

	def is_duplicate(self, root, s):
		if root is None:
			return '$'
		left = self.is_duplicate(root.left, s)
		right = self.is_duplicate(root.right, s)
		s = left + ',' + right + ',' + str(root.data)
		if s in self.d:
			self.d[s] += 1
			if self.d[s] == 2:
				self.ans.append(root)
		else:
			self.d[s] = 1
		return s

	def printAllDups(self, root):
		self.d = {}
		self.ans = []
		self.is_duplicate(root, '')
		self.ans.sort(key=lambda x: x.data)
		return self.ans


class Solution:

	def printAllDups(self, root):

		def inorder(node, m):
			if not node:
				return ''
			Str = '('
			Str += inorder(node.left, m)
			Str += str(node.data)
			Str += inorder(node.right, m)
			Str += ')'
			if Str in m and m[Str] == 1:
				ans.append([node.data, node])
			if Str in m:
				m[Str] += 1
			else:
				m[Str] = 1
			return Str
		m = dict()
		ans = []
		inorder(root, m)
		ans.sort(key=lambda x: x[0])
		res = []
		for (x, y) in ans:
			res.append(y)
		return res


class Solution:

	def printAllDups(self, root):
		dict = {}
		ans = []
		self.helper(root, dict, ans)
		ans.sort(key=lambda x: x.data)
		return ans

	def helper(self, root, dict, ans):
		if root is None:
			return '$'
		left = self.helper(root.left, dict, ans)
		right = self.helper(root.right, dict, ans)
		sums = left + ',' + str(root.data) + ',' + right
		if sums in dict:
			dict[sums] += 1
			if dict[sums] == 2:
				ans.append(root)
		else:
			dict[sums] = 1
		return sums


class Solution:

	def printAllDups(self, root):
		d = {}
		res = []

		def fun(root):
			if root == None:
				return 'N'
			s = ','.join([str(root.data), fun(root.left), fun(root.right)])
			if s in d:
				d[s] = d[s] + 1
				if d[s] == 2:
					res.append(root)
			else:
				d[s] = 1
			return s
		fun(root)
		res.sort(key=lambda x: x.data)
		return res


class Solution:

	def printAllDups(self, root):

		def dfs(root, dic):
			if not root:
				return '#'
			left = dfs(root.left, dic)
			right = dfs(root.right, dic)
			s = str(root.data) + ',' + left + ',' + right
			if s not in dic:
				dic[s] = 0
			else:
				dic[s] += 1
				if dic[s] == 1:
					self.ans.append(root)
			return s
		dic = {}
		self.ans = []
		dfs(root, dic)
		return sorted(self.ans, key=lambda x: x.data)


import collections
import numpy

class Solution:

	def printAllDups(self, root):
		d = collections.defaultdict(list)
		ans = []

		def inorder(root):
			if not root:
				return 'N'
			left = inorder(root.left)
			right = inorder(root.right)
			s = ','.join([str(root.data), left, right])
			if s in d:
				d[s] += 1
				if d[s] == 2:
					ans.append(root)
			else:
				d[s] = 1
			return s
		inorder(root)
		ans.sort(key=lambda x: x.data)
		return ans


class Solution:

	def findDuplicates(self, root, S, dict, ans):
		if root is None:
			return 'N'
		leftAns = self.findDuplicates(root.left, S, dict, ans)
		rightAns = self.findDuplicates(root.right, S, dict, ans)
		S = str(root.data) + ',' + leftAns + ',' + rightAns
		if S in dict:
			dict[S] += 1
			if dict[S] == 2:
				ans.append(root)
		else:
			dict[S] = 1
		return S

	def printAllDups(self, root):
		dict = {}
		S = ''
		ans = []
		self.findDuplicates(root, S, dict, ans)
		ans.sort(key=lambda x: x.data)
		return ans


from collections import defaultdict

class Solution:

	def printAllDups(self, root):
		dic = defaultdict(list)

		def manu(root):
			if root is None:
				return 'N'
			x = manu(root.left)
			y = manu(root.right)
			s = str(root.data) + x + y
			if len(dic[s]) == 1 and dic[s][0][0] == x and (dic[s][0][1] == y):
				res.append([root.data, len(s), root])
			dic[s].append([x, y])
			return s
		res = []
		manu(root)
		res = sorted(res, key=lambda sub: (sub[0], sub[1]))
		a = []
		for i in res:
			a.append(i[2])
		return a


class Solution:

	def f(self, root, d, li):
		if root == None:
			return (d, 'N')
		s = ''
		(d, l) = self.f(root.left, d, li)
		(d, r) = self.f(root.right, d, li)
		s = str(root.data) + 'L' + l + 'R' + r
		if s in d and d[s] == 1:
			li.append(root)
		d[s] = d.get(s, 0) + 1
		return (d, s)

	def printAllDups(self, root):
		li = []
		d = dict()
		(d, s) = self.f(root, d, li)
		li.sort(key=lambda li: li.data)
		return li


class Solution:

	def printAllDups(self, root):
		mp = set()
		ans = dict()

		def finddup(root):
			if root == None:
				return '$'
			left = finddup(root.left)
			right = finddup(root.right)
			val = '$' + str(root.data) + '$' + left + '$' + right
			if val not in mp:
				mp.add(val)
			else:
				ls1 = val.split('$')
				ls1 = [int(i) for i in ls1 if i != '']
				s1 = ls1
				ans[val] = [root, s1]
			return val
		finddup(root)
		ls = []
		strs = []
		for i in ans:
			ls.append([ans[i][0], ans[i][1]])
		ls = sorted(ls, key=lambda x: (x[1], len(x[1])))
		res = []
		for i in ls:
			res.append(i[0])
			strs.append(i[1])
		return res


class Solution:

	def store(self, root):
		if root is None:
			return '$'
		subtree = str(root.data) + ',' + self.store(root.left) + ',' + self.store(root.right)
		try:
			self.subtree[subtree] = self.subtree[subtree] + 1
		except:
			self.subtree[subtree] = 1
		return subtree

	def deserialize(self, arr):
		if arr[self.t] == '$':
			return None
		root = Node(arr[self.t])
		self.t += 1
		root.left = self.deserialize(arr)
		self.t += 1
		root.right = self.deserialize(arr)
		return root

	def printAllDups(self, root):
		self.t = 0
		duplicate = []
		output = []
		self.subtree = {}
		self.store(root)
		for key in self.subtree:
			if self.subtree[key] > 1:
				duplicate.append(key.split(','))
		for tree in sorted(duplicate, key=lambda x: int(x[0])):
			out = self.deserialize(tree)
			output.append(out)
			self.t = 0
		return output


class Solution:

	def DuplicateSubtree(self, root, dict, ans):
		if root == None:
			return '$'
		l = self.DuplicateSubtree(root.left, dict, ans)
		r = self.DuplicateSubtree(root.right, dict, ans)
		val = str(root.data) + '-' + l + '-' + r
		if val in dict:
			if dict[val] == 1:
				ans[0].append(root)
			dict[val] += 1
		else:
			dict[val] = 1
		return val

	def printAllDups(self, root):

		def Compare(val):
			return val.data
		ans = [[]]
		dict = {}
		self.DuplicateSubtree(root, dict, ans)
		ans[0].sort(key=Compare)
		return ans[0]


class Solution:

	def printAllDups(self, root):
		output = []
		self.findDuplicates(root, set(), set(), output)
		srt_output = []
		for item in output:
			traversal = self.preOrderTraversal(item)
			srt_output.append((item, traversal))
		srt_output.sort(key=lambda x: x[1])
		return [item[0] for item in srt_output]

	def preOrderTraversal(self, root):
		if root is None:
			return []
		output = [root.data]
		output += self.preOrderTraversal(root.left)
		output += self.preOrderTraversal(root.right)
		return output

	def findDuplicates(self, root, store, check, output):
		if root is None:
			return 'n'
		left = self.findDuplicates(root.left, store, check, output)
		right = self.findDuplicates(root.right, store, check, output)
		tree = str(root.data) + ' ' + left + ' ' + right
		if tree in store and tree not in check:
			output.append(root)
		if tree in store:
			check.add(tree)
		store.add(tree)
		return tree