Given the root of a n-ary tree find the number of duplicate subtrees in the n-ary tree. Two trees are duplicates if they have the same structure with the same node values.
Example 1:
Input:
1 N 2 2 3 N 4 N 4 4 3 N N N N N
Output: 
2
Explanation: 
[4], [3] are duplicate subtree.
Example 2:
Input:
1 N 2 3 N 4 5 6 N N N N
Output: 
0
Explanation: 
No duplicate subtree found.
Your Task:
You don't need to read input or print anything. Your task is to complete the function duplicateSubtreeNaryTree() which takes the root of the n-ary tree as input and returns an integer value as a number of duplicate subtrees.
Expected Time Complexity: O(n), n is the total no of nodes
Expected Space Complexity: O(n^{2})
Constraints:
   1 <= n < 10^{3}
   1 <= node.key< 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Starter code: #User function Template for python3



'''

class Node:

	def __init__(self, key, children=None):

		self.key = key

		self.children = children or []

	

	def __str__(self):

		return str(self.key)

'''



class Solution:

    def duplicateSubtreeNaryTree(self, root):

        #code here

Solutions:
class Solution:

	def solve(self, root, d):
		s = str(root.key)
		for i in root.children:
			s += self.solve(i, d)
		d[s] = d.get(s, 0) + 1
		return s

	def duplicateSubtreeNaryTree(self, root):
		d = {}
		self.solve(root, d)
		c = 0
		for x in d:
			if d[x] > 1:
				c += 1
		return c


class Solution:

	def duplicateSubtreeNaryTree(self, root):

		def getSubtreeIdentifier(node):
			if not node:
				return ''
			subtree_identifiers = []
			for child in node.children:
				subtree_identifier = getSubtreeIdentifier(child)
				subtree_identifiers.append(subtree_identifier)
			subtree_identifiers.sort()
			subtree_identifier = str(node.key) + ',' + ','.join(subtree_identifiers)
			subtree_counts[subtree_identifier] = subtree_counts.get(subtree_identifier, 0) + 1
			return subtree_identifier
		subtree_counts = {}
		getSubtreeIdentifier(root)
		duplicate_count = 0
		for count in subtree_counts.values():
			if count > 1:
				duplicate_count += 1
		return duplicate_count


class Solution:

	def duplicateSubtreeNaryTree(self, root):

		def traverse(node):
			if not node:
				return '#'
			subtree = str(node.key)
			for child in node.children:
				subtree += traverse(child)
			if subtree in subtrees:
				subtrees[subtree] += 1
			else:
				subtrees[subtree] = 1
			return subtree
		subtrees = {}
		traverse(root)
		return sum((freq > 1 for freq in subtrees.values()))


class Solution:

	def duplicateSubtreeNaryTree(self, root):

		def solve(root):
			if root == None:
				return ''
			res = str(root.key)
			for i in root.children:
				res += '*' + solve(i)
			if res not in d1:
				d1[res] = 1
			else:
				d1[res] += 1
			return res
		d1 = {}
		solve(root)
		ans = 0
		for (i, v) in d1.items():
			if v > 1:
				ans += 1
		return ans


class Solution:

	def recSol(self, node):
		repre = (node.key, tuple(sorted([self.recSol(child) for child in node.children])))
		if repre in self.HashTab:
			if self.HashTab[repre] not in self.duplicated:
				self.duplicated.update([self.HashTab[repre]])
		else:
			self.HashTab[repre] = len(self.HashTab)
		return self.HashTab[repre]

	def duplicateSubtreeNaryTree(self, root):
		self.duplicated = set()
		self.sameVal = 0
		self.HashTab = {}
		self.recSol(root)
		return len(self.duplicated)


class Solution:

	def recSol(self, node):
		if node is None:
			return -1
		repre = (node.key, tuple(sorted([self.recSol(child) for child in node.children])))
		if repre in self.HashTab:
			if self.HashTab[repre] not in self.duplicated:
				self.sameVal += 1
				self.duplicated.update([self.HashTab[repre]])
		else:
			self.HashTab[repre] = self.count
			self.count += 1
		return self.HashTab[repre]

	def duplicateSubtreeNaryTree(self, root):
		self.duplicated = set()
		self.sameVal = 0
		self.HashTab = {}
		self.count = 0
		self.recSol(root)
		return self.sameVal


class Solution:

	def cst(self, root, sp):
		s = str(root.key)
		for y in root.children:
			s += self.cst(y, sp)
		sp[s] = sp.get(s, 0) + 1
		return s

	def duplicateSubtreeNaryTree(self, root):
		sp = {}
		self.cst(root, sp)
		c = 0
		for x in sp:
			if sp[x] > 1:
				c += 1
		return c


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		d = dict()

		def dfs(root):
			count = 1
			for i in root.children:
				x = dfs(i)
				count = count + x
			if d.get(count) != None:
				d[count].append(root)
			if d.get(count) == None:
				d[count] = [root]
			return count
		dfs(root)

		def check(root1, root2):
			if root1.key != root2.key:
				return False
			if len(root1.children) != len(root2.children):
				return False
			y = True
			for i in range(len(root1.children)):
				y = y and check(root1.chilren[i], root2.children[i])
			return y
		d1 = dict()
		for i in d.keys():
			for j in range(len(d[i])):
				for k in range(j + 1, len(d[i])):
					if check(d[i][j], d[i][k]):
						d1[d[i][j].key] = True
		return len(d1.keys())


class Solution:

	def cst(self, root, sp):
		s = str(root.key)
		for y in root.children:
			s += self.cst(y, sp)
		sp[s] = sp.get(s, 0) + 1
		return s

	def duplicateSubtreeNaryTree(self, root):
		sp = {}
		self.cst(root, sp)
		cnt = 0
		for i in sp:
			if sp[i] > 1:
				cnt += 1
		return cnt


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		m = {}

		def solve(root):
			value = str(root.key)
			for c in root.children:
				value += solve(c)
			m[value] = m.get(value, 0) + 1
			return value
		solve(root)
		res = 0
		for i in m:
			if m[i] > 1:
				res += 1
		return res


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		paths = {}

		def dfs(ptr):
			suffix = '' if ptr.children is None or len(ptr.children) == 0 else ''.join(list(map(lambda n: dfs(n), ptr.children)))
			nid = ':' + str(ptr.key) + suffix
			paths[nid] = paths.get(nid, 0) + 1
			return nid
		dfs(root)
		count = 0
		for (k, v) in paths.items():
			count += 1 if v > 1 else 0
		return count


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		d = {}
		func(root, d)
		c = 0
		for i in d:
			if d[i] > 1:
				c += 1
		return c

def func(root, d):
	if root == None:
		return ''
	s = str(root.key)
	for i in root.children:
		s += '$' + func(i, d)
	if s in d:
		d[s] += 1
	else:
		d[s] = 1
	return s


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		from collections import Counter
		c = Counter()

		def dfs(n):
			nonlocal c
			if not n:
				return '#'
			key = '{0} {1}'.format(n.key, ' '.join((dfs(nxt) for nxt in n.children)))
			c[key] += 1
			return key
		dfs(root)
		return sum((v > 1 for v in c.values()))


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		res = []
		hmap = {}

		def recurse(node):
			p = str(node.key) + '#'
			for child in node.children:
				p += recurse(child)
			if p not in hmap:
				hmap[p] = 0
			hmap[p] += 1
			return p
		recurse(root)
		ans = 0
		for val in hmap.values():
			if val > 1:
				ans += 1
		return ans


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		mp = {}

		def postorder(root):
			if root == None:
				return ''
			ans = ''
			for child in root.children:
				ans += postorder(child) + '*'
			ans += str(root.key) + '*'
			mp[ans] = 1 + mp.get(ans, 0)
			return ans
		count = 0
		postorder(root)
		for i in mp:
			if mp[i] > 1:
				count += 1
		return count


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		freq = defaultdict(int)

		def traverse(node):
			if not node:
				return '#'
			subtree = str(node.key)
			for child in node.children:
				subtree += traverse(child)
			freq[subtree] += 1
			return subtree
		traverse(root)
		count = 0
		for key in freq:
			if freq[key] > 1:
				count += 1
		return count


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		d = {}
		self.compute(root, d)
		res = 0
		for (_, count) in d.items():
			if count > 1:
				res += 1
		return res

	def compute(self, root, d):
		cur_value = root.key
		for ch in root.children:
			self.compute(ch, d)
			cur_value += ch.value * 10
		if cur_value not in d:
			d[cur_value] = 0
		d[cur_value] += 1
		root.value = cur_value


class Solution:

	def __init__(self):
		self.dic = dict()

	def helper(self, node):
		temp = str(node.key)
		for child in node.children:
			t = self.helper(child)
			temp = str(temp) + str(t) + 'x'
		if temp not in self.dic:
			self.dic[temp] = 0
		self.dic[temp] += 1
		return temp

	def duplicateSubtreeNaryTree(self, root):
		self.helper(root)
		ans = 0
		for key in self.dic.keys():
			if self.dic[key] > 1:
				ans += 1
		return ans


from collections import defaultdict

class Solution:

	def duplicateSubtreeNaryTree(self, root):
		m = {}

		def dfs(node):
			if not node:
				return ''
			s = str(node.key)
			for i in node.children:
				s += dfs(i)
			if s in m:
				m[s] += 1
			else:
				m[s] = 1
			return s + '*'
		dfs(root)
		ans = 0
		for i in m:
			if m[i] > 1:
				ans += 1
		return ans


class Solution:

	def __init__(self):
		self.ans = 0
		self.m = {}

	def solve(self, root):
		if not root:
			return ''
		s = str(root.key) + ' '
		for c in root.children:
			s += self.solve(c) + ' '
		if s in self.m and self.m[s] == 1:
			self.ans += 1
		self.m[s] = self.m.get(s, 0) + 1
		return s

	def duplicateSubtreeNaryTree(self, root):
		self.solve(root)
		return self.ans


class Solution:
	(ids, cur_id, unique_trees) = ({}, 0, set())

	def duplicateSubtreeNaryTree(self, root):
		(self.ids, self.cur_id, self.unique_trees) = ({}, 0, set())
		self.dfs(root)
		return len(self.unique_trees)

	def dfs(self, node):
		cur = [str(node.key)]
		for child in node.children:
			cur.append(self.dfs(child))
		cur = '#'.join(cur)
		if self.ids.get(cur, -1) == -1:
			self.cur_id += 1
			self.ids[cur] = self.cur_id
		else:
			self.unique_trees.add(self.ids[cur])
		return str(self.ids[cur])


class Solution:

	def __init__(self):
		self.map = {}

	def duplicateSubtreeNaryTree(self, root):
		answer = 0
		self.solve(root)
		for x in self.map:
			if self.map[x] > 1:
				answer += 1
		return answer

	def solve(self, root: 'Node') -> str:
		s = str(root.key)
		for y in root.children:
			s += self.solve(y)
		self.map[s] = self.map.get(s, 0) + 1
		return s


class Solution:

	def __init__(self):
		self.map = {}

	def duplicateSubtreeNaryTree(self, root: 'Node') -> int:
		ans = 0
		self.solve(root)
		for e in self.map:
			if self.map[e] > 1:
				ans += 1
		return ans

	def solve(self, root: 'Node') -> str:
		s = str(root.key)
		for nei in root.children:
			s += self.solve(nei)
		self.map[s] = self.map.get(s, 0) + 1
		return s


class Solution:

	def cst(self, root, s):
		a = str(root.key)
		for i in root.children:
			a += self.cst(i, s)
		s[a] = s.get(a, 0) + 1
		return a

	def duplicateSubtreeNaryTree(self, root):
		t = {}
		self.cst(root, t)
		ans = 0
		for i in t:
			if t[i] > 1:
				ans += 1
		return ans


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		self.map = {}

		def solve(root):
			if root is None:
				return ''
			returnValue = root.__str__()
			for ch in root.children:
				returnValue = returnValue + '#' + solve(ch)
			self.map[returnValue] = self.map.get(returnValue, 0) + 1
			return returnValue
		solve(root)
		ans = 0
		for val in self.map.values():
			if val > 1:
				ans += 1
		return ans


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		hash = {}

		def count_sub_tree(node):
			if not node:
				return ''
			s = str(node.key)
			for child in node.children:
				s += count_sub_tree(child)
			hash[s] = hash.get(s, 0) + 1
			return s
		count_sub_tree(root)
		res = 0
		for sub_tree in hash:
			if hash[sub_tree] > 1:
				res += 1
		return res


class Solution:

	def duplicateSubtreeNaryTree(self, root):

		def traverse(node):
			nonlocal count, subtrees
			if not node:
				return ''
			subtree = str(node.key)
			for child in node.children:
				subtree += traverse(child)
			if subtree in subtrees and subtrees[subtree] == 1:
				count += 1
				subtrees[subtree] = 2
			elif subtree not in subtrees:
				subtrees[subtree] = 1
			return subtree
		count = 0
		subtrees = {}
		traverse(root)
		return count


import collections

class Solution:

	def duplicateSubtreeNaryTree(self, root):
		PRIME = 1337
		hashes = collections.defaultdict(int)

		def dfs(r):
			nonlocal hashes
			if not r:
				return 1
			ret = r.key
			for i in range(len(r.children)):
				ret += (i + 1) * dfs(r.children[i])
			ret = ret * PRIME
			hashes[ret] += 1
			return ret
		dfs(root)
		ans = 0
		for (k, v) in hashes.items():
			ans += v > 1
		return ans


class Solution:

	def solve(self, root, mp):
		st = str(root.key) + ':'
		arr = []
		for i in root.children:
			arr.append(self.solve(i, mp))
		arr.sort()
		for i in arr:
			st += i + ','
		if st in mp:
			mp[st] += 1
		else:
			mp[st] = 1
		return st

	def duplicateSubtreeNaryTree(self, root):
		(count, mp) = (0, {})
		self.solve(root, mp)
		for i in mp:
			if mp[i] > 1:
				count += 1
		return count


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		d = {}

		def trav(node):
			if not node:
				return '#'
			s = str(node.key) + ''.join((trav(n) for n in node.children))
			d[s] = d.get(s, 0) + 1
			return s
		trav(root)
		op = 0
		for i in d:
			if d[i] >= 2:
				op += 1
		return op


class Solution:

	def duplicateSubtreeNaryTree(self, root):
		d = {}

		def duplicateSubTree(root):
			if root == None:
				return '()'
			subtree = ''
			for child in root.children:
				subtree += duplicateSubTree(child)
			d['(' + str(root.key) + subtree + ')'] = d.get('(' + str(root.key) + subtree + ')', 0) + 1
			return '(' + str(root.key) + subtree + ')'
		duplicateSubTree(root)
		ans = 0
		for key in d.keys():
			if d[key] >= 2:
				ans += 1
		return ans