You are given a root node of a binary Tree and each node of the binary tree is assigned a value and you are also given an integer k and you have to return the count of Good subtrees of this binary Tree . Good subtree is a subtree such that the number of distinct values in this subtree is less than or equal to k.
Note: Subtree of a node consists of that node and all nodes of the subtrees of left and right child  of that node  if they exist .
Example 1:
Input:
k=2
Output: 4
Explanation:
We can see all leaves 3,4,5 form good subtrees as number of distinct values in subtrees is 1 which is less than k which is given as 2,now  subtree which starts at 2 and has 3 as left node  is also a good subtree because the count of distinct values is 2 which is equal to k so overall 4 good subtrees.
Example 2:
Input:
k=1
Output: 4
Explanation:
we can see all leaves 2,2 form good subtrees as number of distinct values in subtrees is 1 which is equal to k which is given as 1, now  both subtrees which starts at 2 and has 2 as child also forms  a good subtree because count of distinct values is 1 which is equal to k so overall 4 good subtrees.
Your Task:
You don't need to read input or print anything. Your task is to complete the function goodSubtrees() which takes root of binary tree  and an integer k respectively and you have to  return the count of good subtrees .
Expected Time Complexity: O(n*k)
Expected Space Complexity: O(n+n*k), where n is the size of recursion stack.
Constraints:
1<=n<=10^{5} (Number of nodes in binary Tree)
1<=node.data<=25
1<=k<=20
The sum of n over all test cases won't exceed 5*10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph traversal

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 goodSubtrees(self, root, k):

        #code here



Solutions:
class Solution:

	def __init__(self):
		self.count = 0

	def dfs(self, root, k):
		if root == None:
			return []
		sett = []
		left = self.dfs(root.left, k)
		sett.extend(left)
		right = self.dfs(root.right, k)
		sett.extend(right)
		if root.data not in sett:
			sett.append(root.data)
		sett = [*set(sett)]
		if len(sett) <= k:
			self.count += 1
		return sett

	def goodSubtrees(self, root, k):
		self.dfs(root, k)
		return self.count


class Solution:

	def goodSubtrees(self, root, k):
		ans = 0

		def dfs(r):
			nonlocal ans
			if not r:
				return []
			seen = set([r.data])
			l = dfs(r.left)
			r = dfs(r.right)
			for x in l:
				seen.add(x)
			for x in r:
				seen.add(x)
			if len(seen) <= k:
				ans += 1
			return seen
		dfs(root)
		return ans


class Solution:

	def Solve(self, root, k, marker):
		if not root:
			return set()
		merge = self.Solve(root.left, k, marker).union(self.Solve(root.right, k, marker))
		merge.add(root.data)
		if len(merge) <= k:
			marker[0] += 1
		return merge

	def goodSubtrees(self, root, k):
		a = [0]
		self.Solve(root, k, a)
		return a[0]


class Solution:

	def goodSubtrees(self, root, k):

		def answer(root, k, ans):
			if root == None:
				return set()
			else:
				lset = answer(root.left, k, ans)
				rset = answer(root.right, k, ans)
				lset.add(root.data)
				lset.update(rset)
				if len(lset) <= k:
					ans[0] += 1
				return lset
		ans = [0]
		answer(root, k, ans)
		return ans[0]


class Solution:

	def goodSubtrees(self, root, k):
		ans = 0

		def solve(root):
			nonlocal ans
			if not root:
				return set()
			temp = set()
			temp.add(root.data)
			temp |= solve(root.left)
			temp |= solve(root.right)
			if len(temp) <= k:
				ans += 1
			return temp
		solve(root)
		return ans


class Solution:

	def goodSubtrees(self, root, k):
		good_count = 0

		def impl(node: Node):
			nonlocal good_count
			result = {node.data}
			dl = impl(node.left) if node.left is not None else set()
			dr = impl(node.right) if node.right is not None else set()
			result = result.union(dl, dr)
			good_count += 1 if len(result) <= k else 0
			return result
		impl(root)
		return good_count


class Solution:

	def goodSubtrees(self, root, k):
		self.res = 0

		def postorder(node, k):
			if not node:
				return set()
			left = postorder(node.left, k)
			right = postorder(node.right, k)
			left = left.union(right)
			left.add(node.data)
			if len(left) <= k:
				self.res += 1
			return left
		postorder(root, k)
		return self.res


class Solution:
	ans = 0

	def goodSubtrees(self, root, k):
		self.ans = 0
		self.check(root, k)
		return self.ans

	def check(self, root, k):
		if root:
			l = self.check(root.left, k)
			r = self.check(root.right, k)
			l = l.union(r)
			l.add(root.data)
			self.ans += len(l) <= k
			return l
		else:
			return set()


class Solution:

	def goodSubtrees(self, root, k):
		self.count = 0

		def distinct(node):
			if not node:
				return set()
			s = set()
			s.add(node.data)
			s.update(distinct(node.left))
			s.update(distinct(node.right))
			if len(s) <= k:
				self.count += 1
			return s
		distinct(root)
		return self.count


class Solution:

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

	def dfs(self, root):
		if root.left == None and root.right == None:
			self.map[root] = {root.data}
			self.ans += 1
			return
		elif root.left == None:
			self.dfs(root.right)
			self.map[root] = self.map[root.right].union({root.data})
		elif root.right == None:
			self.dfs(root.left)
			self.map[root] = self.map[root.left].union({root.data})
		else:
			self.dfs(root.left)
			self.dfs(root.right)
			self.map[root] = self.map[root.left].union(self.map[root.right]).union({root.data})
		if len(self.map[root]) <= k:
			self.ans += 1

	def goodSubtrees(self, root, k):
		self.dfs(root)
		return self.ans


class Solution:

	def goodSubtrees(self, root, k):
		ans = []

		def solve(root):
			if root == None:
				return (set(), 0)
			ans = set()
			l = solve(root.left)
			r = solve(root.right)
			for i in l[0]:
				ans.add(i)
			for j in r[0]:
				ans.add(j)
			ans.add(root.data)
			if len(ans) <= k:
				return (ans, l[1] + r[1] + 1)
			else:
				return (ans, l[1] + r[1])
		return solve(root)[1]


from collections import defaultdict

class Solution:

	def goodSubtrees(self, root, k):
		count = [0]

		def dfs(node):
			if not node:
				return []
			left_vals = dfs(node.left)
			right_vals = dfs(node.right)
			vals = left_vals + right_vals + [node.data]
			freq = defaultdict(int)
			distinct_count = 0
			for val in vals:
				freq[val] += 1
				if freq[val] == 1:
					distinct_count += 1
			if distinct_count <= k:
				count[0] += 1
			return list(freq.keys())
		dfs(root)
		return count[0]


class Solution:

	def goodSubtrees(self, root, k):
		res = 0

		def recur(root):
			if not root:
				return set()
			left = recur(root.left)
			right = recur(root.right)
			left.update(right)
			left.add(root.data)
			if len(left) <= k:
				nonlocal res
				res += 1
			return left
		recur(root)
		return res


class Solution:

	def goodSubtrees(self, root, k):

		def solve(root, k, ans):
			if root is None:
				return set()
			left = solve(root.left, k, ans)
			right = solve(root.right, k, ans)
			left.add(root.data)
			left.update(right)
			if len(left) <= k:
				ans[0] += 1
			return left
		ans = [0]
		solve(root, k, ans)
		return ans[0]


class Solution:

	def returnTotalGoodSubtrees(self, root, k):
		if not root:
			return [0, set()]
		leftPart = self.returnTotalGoodSubtrees(root.left, k)
		rightPart = self.returnTotalGoodSubtrees(root.right, k)
		myset = leftPart[1].union(rightPart[1])
		myset.add(root.data)
		goodSubtrees = leftPart[0] + rightPart[0] + 1 if len(myset) <= k else leftPart[0] + rightPart[0]
		return [goodSubtrees, myset]

	def goodSubtrees(self, root, k):
		return self.returnTotalGoodSubtrees(root, k)[0]


class Solution:

	def goodSubtrees(self, root, k):
		ans = 0

		def walk(node):
			nonlocal ans
			if not node:
				return set()
			left = walk(node.left)
			right = walk(node.right)
			r = left.union(right).union({node.data})
			if len(r) <= k:
				ans += 1
			return r
		walk(root)
		return ans


class Solution:

	def goodSubtrees(self, root, k):
		count_t = [0]
		root.dist = 0

		def dfs(root):
			count = set()
			count_l = set()
			count_r = set()
			if not root:
				return set()
			count_l = dfs(root.left)
			count_r = dfs(root.right)
			count.update(count_l)
			count.update(count_r)
			count.add(root.data)
			if len(count) <= k:
				count_t[0] += 1
			return count
		try:
			dfs(root)
			return count_t[0]
		except Exception as e:
			print('e', e, exc_info=True)


class Solution:

	def goodSubtrees(self, root, k):

		def fun(root):
			ans = set([root.data])
			b = 0
			d = 0
			if root.left:
				(a, b) = fun(root.left)
				for i in a:
					ans.add(i)
			if root.right:
				(a, d) = fun(root.right)
				for i in a:
					ans.add(i)
			if len(ans) <= k:
				b += 1
			return (ans, b + d)
		(a, finalAns) = fun(root)
		return finalAns


class Solution:

	def goodSubtrees(self, root, k):

		def s(root, k, ans):
			if root is None:
				return set()
			l = s(root.left, k, ans)
			r = s(root.right, k, ans)
			l.add(root.data)
			l.update(r)
			if len(l) <= k:
				ans[0] += 1
			return l
		ans = [0]
		s(root, k, ans)
		return ans[0]


class Solution:

	def getAns(self, root, k, sett):
		if root == None:
			return 0
		lset = set()
		rset = set()
		ans = 0
		ans += self.getAns(root.left, k, lset)
		ans += self.getAns(root.right, k, rset)
		sett.update(lset | rset)
		sett.add(root.data)
		if len(sett) <= k:
			ans += 1
		return ans

	def goodSubtrees(self, root, k):
		return self.getAns(root, k, set())


class Solution:

	def preorder(self, root, st, k, good):
		if root is None:
			return
		st[root] = [0] * 26
		st[root][root.data] = 1
		st[root][0] = 1
		self.preorder(root.left, st, k, good)
		self.preorder(root.right, st, k, good)
		for j in range(1, 26):
			if root.left:
				if st[root.left][j] == 1 and st[root][j] == 0:
					st[root][0] += 1
					st[root][j] = 1
			if root.right:
				if st[root.right][j] == 1 and st[root][j] == 0:
					st[root][0] += 1
					st[root][j] = 1
		if st[root][0] <= k:
			good[0] += 1

	def goodSubtrees_v1(self, root, k):
		st = {}
		good = [0]
		self.preorder(root, st, k, good)
		return good[0]

	def goodSubtrees(self, root, k):

		def solve(root):
			if root == None:
				return (set(), 0)
			ans = set()
			l = solve(root.left)
			r = solve(root.right)
			for i in l[0]:
				ans.add(i)
			for j in r[0]:
				ans.add(j)
			ans.add(root.data)
			if len(ans) <= k:
				return (ans, l[1] + r[1] + 1)
			else:
				return (ans, l[1] + r[1])
		return solve(root)[1]


class Solution:

	def goodSubtrees(self, root, n):

		def resol(root):
			if root == None:
				return (set(), 0)
			answer = set()
			leftpointer = resol(root.left)
			rightpointer = resol(root.right)
			for x in leftpointer[0]:
				answer.add(x)
			for y in rightpointer[0]:
				answer.add(y)
			answer.add(root.data)
			if len(answer) <= n:
				return (answer, leftpointer[1] + rightpointer[1] + 1)
			else:
				return (answer, leftpointer[1] + rightpointer[1])
		return resol(root)[1]


class Solution:

	def __init__(self):
		self.count = 0

	def dfs(self, node, k):
		ans = set()
		if node is None:
			return ans
		left = self.dfs(node.left, k)
		right = self.dfs(node.right, k)
		left.update(right)
		left.add(node.data)
		if len(left) <= k:
			self.count += 1
		return left

	def goodSubtrees(self, root, k):
		self.dfs(root, k)
		return self.count


class Solution:

	def goodSubtrees(self, root, k):
		self.ans = 0

		def subTreeSolve(root):
			if root == None:
				return None
			finalSet = set()
			l = subTreeSolve(root.left)
			r = subTreeSolve(root.right)
			finalSet.add(root.data)
			if l:
				finalSet = finalSet | l
			if r:
				finalSet = finalSet | r
			if len(finalSet) <= k:
				self.ans += 1
			return finalSet
		subTreeSolve(root)
		return self.ans


from collections import defaultdict
from collections import deque
from sys import stdin, stdout

class Node:

	def _init_(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def goodSubtrees(self, root, k):

		def count_good_subtrees(node):
			nonlocal count
			if not node:
				return set()
			left_subtree = count_good_subtrees(node.left)
			right_subtree = count_good_subtrees(node.right)
			subtree_values = left_subtree.union(right_subtree)
			subtree_values.add(node.data)
			if len(subtree_values) <= k:
				count += 1
			return subtree_values
		count = 0
		count_good_subtrees(root)
		return count


class Solution:
	cnt = 0

	def fun(self, root, k):
		if root == None:
			return set()
		s = set()
		s.add(root.data)
		t1 = self.fun(root.left, k)
		t2 = self.fun(root.right, k)
		s.update(t1)
		s.update(t2)
		if root.left:
			s.add(root.left.data)
		if root.right:
			s.add(root.right.data)
		if len(s) <= k:
			self.cnt += 1
		return s

	def goodSubtrees(self, root, k):
		self.cnt = 0
		self.fun(root, k)
		return self.cnt


class Solution:

	def goodSubtrees(self, root, k):

		def getNumberOfGoodSubTrees(root, k):
			nonlocal ans
			if root == None:
				return {}
			if root.left == None and root.right == None:
				ans += 1
				d = {}
				d[root.data] = 1
				return d
			leftD = getNumberOfGoodSubTrees(root.left, k)
			rightD = getNumberOfGoodSubTrees(root.right, k)
			for key in leftD.keys():
				rightD[key] = 1
			rightD[root.data] = 1
			if len(rightD.keys()) <= k:
				ans += 1
			return rightD
		ans = 0
		getNumberOfGoodSubTrees(root, k)
		return ans


class Subtree:

	def __init__(self):
		self.uniq = set()

class Solution:

	def goodSubtrees(self, root, k):
		self.count = 0

		def dfs(node):
			if not node:
				return Subtree()
			sub = Subtree()
			sub.uniq.add(node.data)
			(left, right) = (dfs(node.left), dfs(node.right))
			sub.uniq.update(left.uniq)
			sub.uniq.update(right.uniq)
			if len(sub.uniq) <= k:
				self.count += 1
			return sub
		dfs(root)
		return self.count


class Solution:

	def goodSubtrees(self, root, k):
		self.ans = 0

		def help(root):
			srs = set()
			if not root:
				return None
			l = help(root.left)
			r = help(root.right)
			srs.add(root.data)
			if l:
				srs = srs | l
			if r:
				srs = srs | r
			if len(srs) <= k:
				self.ans += 1
			return srs
		help(root)
		return self.ans


class Solution:

	def util(self, root, k, ans):
		if not root:
			return
		mapper = dict()
		mapper[root.data] = 1 + mapper.get(root.data, 0)
		if root.left:
			left = self.util(root.left, k, ans)
			if left:
				mapper.update(left)
		if root.right:
			right = self.util(root.right, k, ans)
			if right:
				mapper.update(right)
		if len(mapper) <= k:
			ans[0] += 1
		return mapper

	def goodSubtrees(self, root, k):
		ans = [0]
		self.util(root, k, ans)
		return ans[0]


class Solution:

	def solve(self, p, k):
		if not p:
			return set()
		if not p.left and (not p.right):
			if k >= 1:
				self.ans += 1
			ans = set()
			ans.add(p.data)
			return ans
		left = self.solve(p.left, k)
		right = self.solve(p.right, k)
		ans = left.union(right)
		ans.add(p.data)
		if len(ans) <= k:
			self.ans += 1
		return ans

	def goodSubtrees(self, root, k):
		self.ans = 0
		self.solve(root, k)
		return self.ans


class Solution:

	def goodSubtrees(self, root, k):
		from collections import deque

class Solution:

	def goodSubtrees(self, root, k):
		global res
		res = 0

		def preOrder(node):
			global res
			if not node:
				return {}
			st = set()
			l = preOrder(node.left)
			r = preOrder(node.right)
			st.add(node.data)
			st = st.union(l)
			st = st.union(r)
			if len(st) <= k:
				res += 1
			return st
		preOrder(root)
		return res


class Solution:

	def distincts(self, root, k):
		s = set()
		if not root:
			return (s, 0)
		s.add(root.data)
		c = 0
		if root.left:
			(s1, c1) = self.distincts(root.left, k)
			c += c1
			s.update(s1)
		if root.right:
			(s2, c2) = self.distincts(root.right, k)
			c += c2
			s.update(s2)
		if len(s) <= k:
			c += 1
		return (s, c)

	def goodSubtrees(self, root, k):
		(s, c) = self.distincts(root, k)
		return c