Given a binary tree and a budget. Assume you are at the root of the tree(level 1), you need to maximise the count of leaf nodes you can visit in your budget if the cost of visiting a leaf node is equal to the level of that leaf node. 
Example 1:
Input: 
                  10
                /    \
               8      2
             /      /   \
            3      3     6
                    \
                     4
and budget = 8
Output: 2
Explanation:
Cost For visiting Leaf Node 3: 3
Cost For visiting Leaf Node 4: 4
Cost For visiting Leaf Node 6: 3
In budget 8 one can visit Max 2 Leaf Nodes.
Example 2:
Input: 
            1
       /   \
      2     3
     / \   / \
    4   5 6   7
and budget = 5
Output: 1
Your Task:
You don't need to read input or print anything. Your task is to complete the function getCount() which takes root node of the tree and a integer denoting the budget as input parameters and returns an integer denoting the count of visited leaf nodes of the tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=T<=10^{3}
1<=N<=10^{4}
1<=budget<=10^{4}

Source: geeksforgeeks | Difficulty: EASY
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 getCount(self,root,n):
        #code here

Solutions:
class Solution:

	def getCount(self, root, n):
		q = [root]
		lev = 0
		m = 0
		while q:
			l = len(q)
			lev += 1
			for i in range(l):
				p = q.pop(0)
				if p.left is None and p.right is None and (n >= lev):
					m += 1
					n -= lev
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return m


class Solution:

	def solve(self, root, l, dic):
		if root == None:
			return
		if root.left == None and root.right == None:
			dic.append(l)
		l += 1
		self.solve(root.left, l, dic)
		self.solve(root.right, l, dic)
		l -= 1

	def getCount(self, root, n):
		dic = []
		self.solve(root, 1, dic)
		dic.sort()
		i = 0
		count = 0
		while n > 0 and i < len(dic):
			if n >= dic[i]:
				count += 1
				n -= dic[i]
			else:
				n = 0
			i += 1
		return count


class Solution:

	def getCount(self, root, n):
		A = []
		self.x(root, A, 1)
		d = 0
		c = 0
		A.sort()
		for i in A:
			if d + i > n:
				return c
			else:
				c += 1
				d += i
		return c

	def x(self, root, A, level):
		if root is None:
			return
		self.x(root.left, A, level + 1)
		self.x(root.right, A, level + 1)
		if root.left is None and root.right is None:
			A.append(level)


class Solution:

	def getCount(self, root, n):
		leaf = 0
		level = 0
		nodes = 0
		q = deque()
		q.append(root)
		while len(q) > 0:
			count = len(q)
			level += 1
			while count > 0:
				num = q.popleft()
				if num.left is None and num.right is None:
					if leaf == n:
						return nodes
					elif leaf > n:
						return nodes - 1
					leaf += level
					nodes += 1
				if num.left != None:
					q.append(num.left)
				if num.right != None:
					q.append(num.right)
				count -= 1
		if leaf <= n:
			return nodes
		return nodes - 1


class Solution:

	def getCount(self, root, n):
		(c, l) = (0, 1)
		s = [root, None]
		while s != []:
			a = s.pop(0)
			if a == None and len(s) == 0:
				break
			elif a == None:
				l += 1
				s += [None]
				continue
			if a.left != None:
				s += [a.left]
			if a.right != None:
				s += [a.right]
			if a.left == None and a.right == None:
				if n - l >= 0:
					c += 1
					n -= l
		return c


class Solution:

	def getCount(self, root, n):
		queue = deque([(root, 1)])
		height = 0
		count = 0
		while queue:
			(node, h) = queue.popleft()
			if node.left is None and node.right is None:
				n -= h
				if n >= 0:
					count += 1
			if node.left is not None:
				queue.append((node.left, h + 1))
			if node.right is not None:
				queue.append((node.right, h + 1))
		return count


class Solution:

	def helper(self, root, costs, level):
		if root == None:
			return
		if root.left is None and root.right is None:
			costs.append(level + 1)
			return
		self.helper(root.left, costs, level + 1)
		self.helper(root.right, costs, level + 1)
		return

	def getCount(self, root, n):
		costs = []
		level = 0
		self.helper(root, costs, level)
		costs.sort()
		ans = 0
		while len(costs) != 0 and n >= costs[0]:
			n = n - costs[0]
			costs.pop(0)
			ans += 1
		return ans


class Solution:

	def getCount(self, root, n):
		ans = 0
		q = [root]
		level = 1
		while len(q) != 0:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
				if node.right == None and node.left == None:
					if n - level >= 0:
						n -= level
						ans += 1
					else:
						return ans
			level += 1
		return ans


import collections

class Solution:

	def getCount(self, root, n):
		level = 1
		q = collections.deque([root])
		cnt = 0
		while q and n > 0:
			for i in range(len(q)):
				node = q.popleft()
				if node.left == None and node.right == None:
					if n - level >= 0:
						n = n - level
						cnt += 1
					else:
						n = 0
						break
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return cnt


class Solution:

	def getCount(self, root, budget):

		def traversal(root):
			if root == None:
				return None
			hd = 1
			q = [[root, hd]]
			while q != []:
				node = q.pop()
				if node[-1] not in dict1:
					if node[0].left == None and node[0].right == None:
						dict1[node[-1]] = 1
				elif node[0].left == None and node[0].right == None:
					dict1[node[-1]] += 1
				hd = node[-1]
				if node[0].left:
					q.append([node[0].left, hd + 1])
				if node[0].right:
					q.append([node[0].right, hd + 1])
		dict1 = dict()
		traversal(root)
		list1 = list(map(lambda x: list(x), sorted(dict1.items(), key=lambda x: x[0])))
		length = len(list1)
		i = 0
		countz = 0
		while i < length and budget > 0:
			budget -= list1[i][0]
			if budget >= 0:
				list1[i][1] -= 1
				countz += 1
			if list1[i][1] == 0:
				i += 1
		return countz
		print(list1)


class Solution:

	def dfs(self, root, level):
		if not root:
			return
		if not root.left and (not root.right):
			self.arr.append(level)
		self.dfs(root.left, level + 1)
		self.dfs(root.right, level + 1)

	def getCount(self, root, n):
		self.arr = []
		self.dfs(root, 1)
		self.arr.sort()
		l = 0
		for i in self.arr:
			x = n - i
			if x < 0:
				break
			else:
				n = x
				l += 1
		return l


class Solution:

	def getCount(self, root, n):
		arr = []
		self.levels(root, arr, 0)
		arr.sort(reverse=True)
		count = 0
		while arr:
			n -= arr.pop()
			if n < 0:
				break
			count += 1
		return count

	def levels(self, root, arr, level):
		if not root:
			return
		level += 1
		if not root.left and (not root.right):
			arr.append(level)
		self.levels(root.left, arr, level)
		self.levels(root.right, arr, level)
		return


class Solution:

	def getCount(self, root, n):
		i = 1
		j = 1
		l = []
		if not root:
			return 0
		if not root.left and (not root.right):
			if n > 0:
				return 1
			else:
				return 0
		self.helper(root.left, i, l)
		self.helper(root.right, j, l)
		s = 0
		c = 0
		l.sort()
		for i in l:
			s += i
			if s <= n:
				c += 1
		return c

	def helper(self, root, i, l):
		if not root:
			return
		if root.left:
			self.helper(root.left, i + 1, l)
		if root.right:
			self.helper(root.right, i + 1, l)
		if not root.left and (not root.right):
			l.append(i + 1)


class Solution:

	def getCount(self, root, n):
		res = []

		def helper(root, k, res):
			if root:
				if not root.left and (not root.right):
					res.append(k)
				helper(root.left, k + 1, res)
				helper(root.right, k + 1, res)
		helper(root, 1, res)
		res.sort()
		cnt = 0
		for i in res:
			if n < 0:
				return cnt - 1
			n -= i
			cnt += 1
			if n == 0:
				return cnt
		return len(res) if n >= 0 else cnt - 1


class Solution:

	def getCount(self, root, n):
		x = []
		d = {}

		def helper(root):
			count = 1
			q = deque()
			if not root:
				return None
			q.append(root)
			while q:
				t = 0
				for i in range(len(q)):
					a = q.popleft()
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					if a.left == None and a.right == None:
						t += 1
				d[count] = t
				x.append(count)
				count += 1
		helper(root)
		ans = 0
		for i in x:
			a = d[i]
			while n >= i and a > 0:
				ans += 1
				n -= i
				a -= 1
		return ans


class Solution:

	def getCount(self, root, n):
		l = []
		q = [[root, 1]]
		c = 0
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			f = 0
			if t.left:
				f = 1
				q.append([t.left, g + 1])
			if t.right:
				f = 1
				q.append([t.right, g + 1])
			if f == 0:
				l.append(g)
			c += 1
		l.sort()
		s = 0
		c = 0
		for i in l:
			s += i
			if s <= n:
				c += 1
			else:
				break
		return c


class Node:

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

class Solution:

	def getCount(self, root, n):
		if root is None:
			return None
		else:
			import collections
			q = collections.deque()
			q.append(root)
			budget = []
			level = 1
			while q:
				for i in range(len(q)):
					node = q.popleft()
					if node:
						if node.left == None and node.right == None:
							budget.append(level)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				level += 1
			budget.sort()
			count = 0
			for i in range(len(budget)):
				n = n - budget[i]
				if n >= 0:
					count += 1
				else:
					break
			return count


class Solution:

	def solve(self, root, l, k):
		if root == None:
			return []
		else:
			if root.left == None and root.right == None:
				l.append(k)
			self.solve(root.left, l, k + 1)
			self.solve(root.right, l, k + 1)
		return l

	def getCount(self, root, n):
		k = 1
		l = []
		self.solve(root, l, k)
		if len(l) == 0:
			return 0
		l = sorted(l)
		c = 0
		for i in range(len(l)):
			if n < l[i]:
				break
			n = n - l[i]
			c += 1
		return c


class Solution:

	def leafNode(self, root, arr, level):
		if root == None:
			return None
		if root.left == None and root.right == None:
			arr.append(level)
		self.leafNode(root.left, arr, level + 1)
		self.leafNode(root.right, arr, level + 1)

	def getCount(self, root, n):
		arr = []
		self.leafNode(root, arr, 1)
		arr.sort()
		ans = 0
		var = 0
		for i in range(len(arr)):
			var = var + arr[i]
			if var <= n:
				ans += 1
		return ans


class Solution:

	def getCount(self, root, n):
		q = [root, None]
		level = 1
		count = 0
		while q:
			t = q.pop(0)
			if not t and q:
				q.append(None)
			elif not t and (not q):
				break
			else:
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
				if not t.left and (not t.right):
					if level <= n:
						count += 1
						n -= level
					else:
						break
				if q[0] == None:
					level += 1
		return count


class Solution:

	def getCount(self, root, n):
		levels = self.levels(root, 1)
		nodes = 0
		levels.sort()
		for i in levels:
			if n - i >= 0:
				n -= i
				nodes += 1
			else:
				break
		return nodes

	def levels(self, root, level):
		ans = []
		if root.left == None and root.right == None:
			ans.append(level)
			return ans
		if root.left:
			l = self.levels(root.left, level + 1)
			ans += l
		if root.right:
			r = self.levels(root.right, level + 1)
			ans += r
		return ans


class Solution:

	def getCount(self, root, n):
		l = []

		def recur(node, level):
			if not node:
				return
			elif node.left and node.right:
				recur(node.left, level + 1)
				recur(node.right, level + 1)
				return
			elif node.right:
				return recur(node.right, level + 1)
			elif node.left:
				return recur(node.left, level + 1)
			l.append(level)
		recur(root, 1)
		l.sort()
		c = 0
		val = 0
		for i in l:
			if val + i <= n:
				val += i
				c += 1
			else:
				return c
		return c


class Solution:

	def getCount(self, root, n):
		if not root:
			return 0
		res = []
		queue = [root]
		level = 1
		while queue:
			qLen = len(queue)
			for i in range(qLen):
				node = queue.pop(0)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				if not node.left and (not node.right):
					res.append(level)
			level += 1
		res.sort()
		count = 0
		for i in res:
			if i <= n:
				n -= i
				count += 1
			else:
				break
		return count


class Solution:

	def getCount(self, root, n):
		q = []
		budget = n
		q.append(root)
		level = 1
		count = 0
		c = 0
		while len(q):
			count = len(q)
			while count > 0:
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				if p.left == None and p.right == None:
					if level > budget:
						pass
					else:
						c += 1
						budget = budget - level
				count -= 1
			level += 1
		return c


class Solution:

	def getCount(self, root, n):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		q = [root]
		l = []
		k = 1
		count = 0
		while len(q) > 0:
			for node in q:
				if node.left:
					l.append(node.left)
				if node.right:
					l.append(node.right)
				if node.left is None and node.right is None:
					n = n - k
					if n < 0:
						break
					count = count + 1
			k = k + 1
			q = l
			l = []
		return count


from collections import defaultdict

class Solution:

	def getCount(self, root, n):
		if root is None:
			return []
		if root.right is None and root.left is None and (root.data >= n):
			return 1
		d = []

		def bfs(node, level):
			if not node:
				return
			if node.left is None and node.right is None:
				d.append(level)
			bfs(node.left, level + 1)
			bfs(node.right, level + 1)
		bfs(root, 1)
		d.sort()
		count = 0
		temp_sum = 0
		for i in range(len(d)):
			temp_sum += d[i]
			count += 1
			if temp_sum > n:
				count -= 1
				break
		return count


class Solution:

	def getCount(self, root, budget):

		def height(root):
			if root == None:
				return 0
			left = height(root.left)
			right = height(root.right)
			return max(left, right) + 1

		def traversal(root, level):
			if root == None:
				return None
			if level == 0:
				if root.left == None and root.right == None:
					list1.append(root.data)
			else:
				traversal(root.left, level - 1)
				traversal(root.right, level - 1)
		tall = height(root)
		list1 = []
		list2 = []
		for i in range(tall):
			traversal(root, i)
			if len(list1) > 0:
				list2.extend([i + 1] * len(list1))
			list1 = []
		list2.sort()
		length = len(list2)
		sum1 = list2[0]
		i = 1
		count = 0
		while sum1 <= budget and i <= length:
			count += 1
			if i >= length:
				return count
			sum1 += list2[i]
			i += 1
		return count


class Solution:

	def __init__(self):
		self.levels = []

	def _traverse(self, root, h):
		if root:
			if not root.left and (not root.right):
				self.levels.append(h)
			self._traverse(root.left, h + 1)
			self._traverse(root.right, h + 1)

	def getCount(self, root, n):
		self._traverse(root, 1)
		self.levels.sort()
		sm = ans = 0
		for level in self.levels:
			if sm + level > n:
				break
			sm += level
			ans += 1
		return ans


class Solution:

	def level(self, root, arr, l):
		if root:
			if root.left == None and root.right == None:
				arr.append(l)
			l += 1
			self.level(root.left, arr, l)
			self.level(root.right, arr, l)

	def getCount(self, root, n):
		ans = []
		l = 1
		self.level(root, ans, l)
		ans.sort()
		count = 0
		for i in ans:
			n -= i
			if n >= 0:
				count += 1
		return count


def get(count, root, st):
	if root:
		if root.left is None and root.right is None:
			if st in count:
				count[st] += 1
			else:
				count[st] = 1
		get(count, root.left, st + 1)
		get(count, root.right, st + 1)

class Solution:

	def getCount(self, root, n):
		count = {}
		get(count, root, 1)
		rechable = 0
		for i in sorted(count):
			while n - i >= 0 and count[i] > 0:
				rechable += 1
				count[i] -= 1
				n = n - i
		return rechable