Given a binary tree, find out whether it contains a duplicate sub-tree of size two or more, or not.
Note: Two same leaf nodes are not considered as subtree as size of a leaf node is one.
Example 1 :
Input : 
               1
             /   \ 
           2       3
         /   \       \    
        4     5       2     
                     /  \    
                    4    5
Output : 1
Explanation : 
    2     
  /   \    
 4     5
is the duplicate sub-tree.
Example 2 :
Input : 
               1
             /   \ 
           2       3
Output: 0
Explanation: There is no duplicate sub-tree 
in the given binary tree.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function dupSub() which takes root of the tree as the only argument and returns 1 if the binary tree contains a duplicate sub-tree of size two or more, else 0.
Constraints:
1 ≤ Number of nodes ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

        '''

class Solution:

    def dupSub(self, root):

        # code here

Solutions:
from collections import defaultdict

class Solution:

	def dupSub(self, root):
		d = defaultdict(int)

		def dfs(root):
			if not root:
				return 'X'
			res = ''
			if not root.left and (not root.right):
				res = str(root.data)
				return res
			res += str(root.data) + '-' + dfs(root.left) + '-' + dfs(root.right)
			d[res] += 1
			return res
		dfs(root)
		for x in d:
			if d[x] > 1:
				return 1
		return 0


class Solution:

	def dupSub(self, root):
		mp = {}
		solution(root, mp)
		for (key, val) in mp.items():
			if val > 1:
				return 1
		return 0

def solution(root, mp):
	if root == None:
		return '#'
	s = ''
	if root.left == None and root.right == None:
		s += str(root.data) + '#'
		return s
	s += str(root.data) + '#'
	s += solution(root.left, mp)
	s += solution(root.right, mp)
	if s not in mp:
		mp[s] = 1
	else:
		mp[s] += 1
	return s


from collections import defaultdict

class Solution:

	def __init__(self):
		self.maps = defaultdict(lambda : 0)

	def dupSubUtil(self, root, type='m'):
		if not root:
			return type
		left = self.dupSubUtil(root.left, 'l')
		right = self.dupSubUtil(root.right, 'r')
		if left != 'l' or right != 'r':
			self.maps[left + str(root.data) + right] += 1
		return left + str(root.data) + right

	def dupSub(self, root):
		self.dupSubUtil(root)
		for (k, v) in self.maps.items():
			if v > 1:
				return 1
		return 0


class Solution:

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

		def fun(root):
			if root == None:
				return '%'
			s = ''
			if root.left == None and root.right == None:
				s = str(root.data)
				return s
			s += str(root.data)
			s += ','
			s += fun(root.left)
			s += ','
			s += fun(root.right)
			if s not in hash:
				hash[s] = 1
			else:
				hash[s] += 1
			return s
		fun(root)
		for i in hash:
			if hash[i] >= 2:
				return 1
		return 0


def duplicate(root, d):
	if root == None:
		return '$'
	s = ''
	if root.left == None and root.right == None:
		s = str(root.data)
		return s
	s = s + str(root.data)
	s += ','
	s = s + duplicate(root.left, d)
	s += ','
	s += duplicate(root.right, d)
	if s not in d:
		d[s] = 1
	else:
		d[s] += 1
	return s

class Solution:

	def dupSub(self, root):
		d = dict()
		duplicate(root, d)
		for i in d.keys():
			if d[i] >= 2:
				return 1
		return 0


from collections import defaultdict

class Solution:

	def dupSub(self, root):

		def solve(root):
			if root is None:
				return [[], '']
			(s, x) = (['('], '(')
			l = solve(root.left)
			s += l[0] + [str(root.data)]
			x += l[1] + str(root.data)
			r = solve(root.right)
			s += r[0] + [')']
			x += r[1] + ')'
			if len(s) > 3 and x in subtrees:
				fl[0] = 1
			subtrees[x] += 1
			return [s, x]
		subtrees = defaultdict(int)
		fl = [0]
		solve(root)
		return fl[0]


class Solution:

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

		def fun(root):
			if root == None:
				return 'N'
			if root.left == None and root.right == None:
				s = str(root.data)
				return s
			s = ','.join([str(root.data), fun(root.left), fun(root.right)])
			if s in d:
				res[0] = 1
			else:
				d[s] = 1
			return s
		fun(root)
		return res[0]


class Solution:

	def dupSub(self, root):
		set_ = set()

		def rec(root):
			if root == None:
				return 'n'
			if root.left == None and root.right == None:
				return str(root.data)
			left = rec(root.left)
			if left == -1:
				return -1
			right = rec(root.right)
			if right == -1:
				return -1
			preorderStr = ','.join([str(root.data), left, right])
			if preorderStr in set_:
				return -1
			else:
				set_.add(preorderStr)
				return preorderStr
		if rec(root) == -1:
			return 1
		return 0


class Info:

	def __init__(self, isDup):
		self.isDup = isDup

def test_duplicate(root1, root2):
	if root1 == None and root2 == None:
		return Info(True)
	elif root1 == None or root2 == None:
		return Info(False)
	else:
		linfo = test_duplicate(root1.left, root2.left)
		rinfo = test_duplicate(root1.right, root2.right)
		if root1.data == root2.data:
			return Info(linfo.isDup and rinfo.isDup)
		else:
			return Info(False)

def check_duplicate(root, hash_map):
	if root == None:
		return
	else:
		if root.left or root.right:
			if root.data in hash_map:
				hash_map[root.data].append(root)
			else:
				hash_map[root.data] = [root]
		check_duplicate(root.left, hash_map)
		check_duplicate(root.right, hash_map)

class Solution:

	def dupSub(self, root):
		hash_map = {}
		check_duplicate(root, hash_map)
		for key in hash_map:
			l = len(hash_map[key])
			if l > 0:
				for i in range(l):
					for j in range(i + 1, l):
						info = test_duplicate(hash_map[key][i], hash_map[key][j])
						if info.isDup:
							return 1
		return 0


class Solution:

	def dupSub(self, root):

		def dfs(root, dic):
			if not root:
				return 'null'
			if not root.left and (not root.right):
				return str(root.data)
			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
			return s
		dic = {}
		res = []
		dfs(root, dic)
		for i in dic:
			if dic[i] >= 1:
				return 1
		return 0


class Solution:

	def __init__(self):
		self.roo = None

	def match(self, root1, root2):
		if not root1 and (not root2):
			return True
		if not root1 or not root2:
			return False
		if not root1.data == root2.data:
			return False
		return self.match(root1.left, root2.left) and self.match(root1.right, root2.right)

	def isleaf(self, root1, root2):
		return root1.left == root1.right and root2.left == root2.right

	def finddup(self, temp, root):
		if not temp and (not root):
			return False
		if not root:
			return False
		if root.data == temp.data and temp != root and (not self.isleaf(root, temp)):
			if self.match(temp, root):
				return True
		return self.finddup(temp, root.left) or self.finddup(temp, root.right)

	def dupSub(self, root):
		self.roo = root
		roo = self.roo
		return self.dupp(root, roo)

	def dupp(self, root, roo):
		if not root:
			return 0
		if self.finddup(root, roo):
			return 1
		return self.dupp(root.left, roo) or self.dupp(root.right, roo)


class Solution:

	def dupSub(self, root):

		def f(root):
			if root == None:
				return '$'
			s = ''
			if root.left == None and root.right == None:
				s = str(root.data)
				return s
			left = f(root.left)
			right = f(root.right)
			s = left + ',' + right + ',' + str(root.data)
			try:
				k[s] += 1
			except:
				k[s] = 1
			return s
		k = {}
		f(root)
		for i in k:
			if k[i] >= 2:
				return 1
		return 0


class Solution:

	def solve(self, root):
		if not root:
			return '$'
		s = ''
		if root.left == None and root.right == None:
			s = str(root.data)
			return s
		s = s + self.solve(root.left) + ',' + str(root.data) + ',' + self.solve(root.right)
		try:
			self.d[s] = self.d[s] + 1
		except:
			self.d[s] = 1
		return s

	def dupSub(self, root):
		self.d = {}
		self.solve(root)
		for i in self.d:
			if self.d[i] >= 2:
				return 1
		return 0


class Solution:

	def dupSub(self, root):

		def f(root):
			if root == None:
				return '$'
			s = ''
			if root.left == None and root.right == None:
				s = str(root.data)
				return s
			w = str(root.data)
			if len(w) == 1:
				w += 'a'
			elif len(w) == 2:
				w += 'b'
			else:
				w += 'c'
			s += w
			s += f(root.left)
			s += f(root.right)
			try:
				k[s] += 1
			except:
				k[s] = 1
			return s
		k = {}
		f(root)
		for i in k:
			if k[i] >= 2:
				return 1
		return 0


class Solution:

	def dupSub(self, root):
		inordertree = []

		def inorder(root):
			if root is None:
				return '*'
			if root.left is None and root.right is None:
				return str(root.data) + '*'
			temp = ''
			temp += str(root.data) + '*'
			temp += inorder(root.left)
			temp += inorder(root.right)
			inordertree.append(temp)
			return temp
		inorder(root)
		md = {}
		for i in inordertree:
			if i not in md:
				md[i] = 1
			else:
				return 1
		return 0


def check(root, m):
	if root == None:
		return '$'
	s = ''
	if root.left == None and root.right == None:
		s = str(root.data)
		return s
	s += str(root.data)
	s = s + ',' + str(check(root.left, m)) + ',' + str(check(root.right, m))
	m[s] = m.get(s, 0) + 1
	return s

class Solution:

	def dupSub(self, root):
		lst = ''
		m = {}
		check(root, m)
		cnt = 0
		for i in m:
			if m[i] >= 2:
				cnt += 1
		return cnt


class Solution:

	def dupSub(self, root):
		map = {}

		def getSubTree(root):
			if not root:
				return '$'
			S = ''
			if root.left is None and root.right is None:
				S = str(root.data)
				return S
			S = S + str(root.data)
			S = S + ','
			S = S + getSubTree(root.left)
			S = S + ','
			S = S + getSubTree(root.right)
			if S not in map:
				map[S] = 1
			else:
				map[S] += 1
			return S
		getSubTree(root)
		for i in map:
			if map[i] >= 2:
				return 1
		return 0


import sys
from collections import deque

class Solution:

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

	def solve(self, root):
		if root == None:
			return '$'
		s = ''
		if root.left == None and root.right == None:
			s += str(root.data)
			return s
		s += str(root.data) + ',' + self.solve(root.left) + ',' + self.solve(root.right)
		if s in self.dic:
			self.dic[s] += 1
		else:
			self.dic[s] = 1
		return s

	def dupSub(self, root):
		self.solve(root)
		for (i, j) in self.dic.items():
			if j >= 2:
				return 1
		return 0


import sys
from collections import deque

class Solution:

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

		def fun(root):
			if root == None:
				return '%'
			s = ''
			if root.left == None and root.right == None:
				s = str(root.data)
				return s
			s += str(root.data)
			s += ','
			s += fun(root.left)
			s += ','
			s += fun(root.right)
			if s not in hash:
				hash[s] = 1
			else:
				hash[s] += 1
			return s
		fun(root)
		for i in hash:
			if hash[i] >= 2:
				return 1
		return 0


class Solution:

	def dupSub(self, root):
		map1 = {}

		def tree_to_str(root):
			if not root:
				return ''
			s = ''
			if root.left == None and root.right == None:
				return str(root.data)
			st1 = str(root.data)
			l = tree_to_str(root.left)
			r = tree_to_str(root.right)
			s = st1 + ' ' + l + ' ' + r
			if s not in map1:
				map1[s] = 1
			else:
				map1[s] += 1
			return s
		tree_to_str(root)
		for item in map1:
			if map1[item] >= 2:
				return 1
		return 0


class Solution:

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

		def fun(root):
			if not root:
				return ''
			s = ''
			if root.left == None and root.right == None:
				return str(root.data)
			temp = str(root.data)
			l = fun(root.left)
			r = fun(root.right)
			s = temp + ' ' + l + ' ' + r
			if s not in m:
				m[s] = 1
			else:
				m[s] += 1
			return s
		fun(root)
		for i in m:
			if m[i] >= 2:
				return 1
		return 0


class Solution:

	def dupSub(self, root):
		mp = set()
		flag = [0]

		def finddup(root):
			if root == None:
				return 'N'
			if root.left == None and root.right == None:
				return str(root.data)
			left = finddup(root.left)
			right = finddup(root.right)
			val = ''
			val = str(root.data) + '$' + left + '$'
			val += right
			if val not in mp:
				mp.add(val)
			else:
				flag[0] = 1
			return val
		finddup(root)
		if flag[0] == 1:
			return 1
		else:
			return 0


from collections import defaultdict

class Solution:

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

	def dupSub(self, root):
		d = dict()
		(d, s) = self.f(root, d)
		for ele in d:
			if d[ele] > 1:
				return 1
		return 0


from collections import defaultdict as dd

def pre_str(head, k1):
	if head:
		a = str(head.data)
		if not head.left and (not head.right):
			return a
		b = pre_str(head.left, k1)
		c = pre_str(head.right, k1)
		val = a + '(' + b + ')(' + c + ')'
		k1[val] += 1
		return val
	return ''

class Solution:

	def dupSub(self, root):
		x1 = dd(int)
		pre_str(root, x1)
		st = 0
		for i in x1:
			if x1[i] >= 2:
				st = 1
				break
		return st


from collections import defaultdict

class Solution:

	def __init__(self):
		self.ans = 0

	def dupSub(self, root):
		subtrees = {}
		res = []

		def postorder(root):
			if not root:
				return 'Null'
			if root.left is None and root.right is None:
				returne = str(root.data)
				return returne
			ans = ''
			ans += str(root.data)
			ans += '_'
			ans += postorder(root.left)
			ans += '_'
			ans += postorder(root.right)
			if ans in subtrees:
				subtrees[ans] += 1
			else:
				subtrees[ans] = 1
			return ans
		k = postorder(root)
		for (i, j) in subtrees.items():
			if j >= 2:
				return 1
		return 0


class Solution:

	def dub(self, root):
		if root is None:
			return '#'
		s = ''
		if root.right is None and root.left is None:
			s = str(root.data)
			return s
		s = s + str(root.data)
		s = s + '+' + self.dub(root.left)
		s = s + '+' + self.dub(root.right)
		if s in self.subtree:
			self.subtree[s] += 1
		else:
			self.subtree[s] = 1
		return s

	def dupSub(self, root):
		self.subtree = {}
		self.dub(root)
		for i in list(self.subtree.values()):
			if i >= 2:
				return 1
		return 0


class Solution:

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

	def dupSub(self, root):
		dict = {}
		self.DuplicateSubtree(root, dict)
		for dic in dict:
			if dict[dic] > 1:
				dollar = 0
				for char in dic:
					if char == '$':
						dollar += 1
				if dollar > 2:
					return 1
		return 0


class Solution:

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

	def dupSub(self, root):
		self.subtree = {}
		self.store(root)
		for key in self.subtree:
			if self.subtree[key] > 1:
				return 1
		return 0


class Solution:

	def solve(self, root):
		if not root:
			return '$'
		s = ''
		if not root.right and (not root.left):
			s = str(root.data)
			return s
		s = s + str(root.data) + ',' + self.solve(root.left) + ',' + self.solve(root.right)
		try:
			self.subtrees[s] = self.subtrees[s] + 1
		except:
			self.subtrees[s] = 1
		return s

	def dupSub(self, root):
		self.subtrees = {}
		test = self.solve(root)
		for key in self.subtrees:
			if self.subtrees[key] > 1:
				return 1
		return 0


class Solution:

	def dupSub(self, root):
		store = set()
		self.findDub(root, set(), store)
		for item in store:
			if len(item.split()) > 3:
				return 1
		return 0

	def findDub(self, root, store, doubles):
		if root is None:
			return 'n'
		left = self.findDub(root.left, store, doubles)
		right = self.findDub(root.right, store, doubles)
		tree = str(root.data) + ' ' + left + ' ' + right
		if tree in store:
			doubles.add(tree)
		else:
			store.add(tree)
		return tree


class Solution:

	def dupSub(self, root):

		def count(s):
			count = 0
			for i in s:
				if i == '-':
					count = count + 1
			return count
		d = dict()

		def dfs(root):
			if root == None:
				return '0'
			d[root] = str(root.data) + '-' + dfs(root.left) + '-' + dfs(root.right)
			return d[root]
		dfs(root)
		d1 = dict()
		for i in d.keys():
			if count(d[i]) == 2:
				continue
			if d1.get(d[i]) != None:
				return 1
			d1[d[i]] = True
		return 0