Given a binary tree, you need to find the number of all root to leaf paths along with their path lengths.
Example 1:
Input:
      3
    /   \
   2     4
Output:
2 2 $
Explanation :
There are 2 roots to leaf paths
of length 2(3 -> 2 and 3 -> 4)
Example 2:
Input:
        10
     /   \
    20    30
   / \    
  40  60
Output:
2 1 $3 2 $
Explanation:
There is 1 root leaf paths of
length 2 and 2 roots to leaf paths
of length 3.
Your Task:
Your task is to complete the function pathCounts that prints the path length and the number of root to leaf paths of this length separated by space.  Every path length and number of root to leaf path should be separated by  "$".
Constraints:
1 <= T <= 30
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:
'''

class Node:

    def __init__(self, value):

        self.left = None

        self.data = value

        self.right = None

'''

# Your task is to complete this function

# Function should print all possible lengths

# print a new at end of function

def pathCounts(root):

    # Code here

Solutions:
def pathCounts(root):
	has = {}

	def fun(root, row):
		if root is None:
			return
		if root.left == None and root.right == None:
			if row in has:
				has[row] += 1
			else:
				has[row] = 1
			return
		fun(root.left, row + 1)
		fun(root.right, row + 1)
	fun(root, 1)
	for (key, value) in has.items():
		print('{} {}'.format(key, value), '$', end='')


def preOrder(p, ans, k):
	if p == None:
		return
	if p.left == None and p.right == None:
		ans[k + 1] = ans.get(k + 1, 0) + 1
	else:
		preOrder(p.left, ans, k + 1)
		preOrder(p.right, ans, k + 1)

def pathCounts(root):
	dict = {}
	preOrder(root, dict, 0)
	ans = []
	for (k, v) in dict.items():
		ans.append((k, v))
	ans.sort()
	for a in ans:
		print(a[0], a[1], '$', end='')


def solve(root, lis, count):
	if root == None:
		return
	count += 1
	if root.left == None and root.right == None:
		lis.append(count)
	solve(root.left, lis, count)
	solve(root.right, lis, count)
	count -= 1

def pathCounts(root):
	lis = []
	ans = []
	solve(root, lis, 0)
	ans = lis.copy()
	ans = set(ans)
	for i in ans:
		k = lis.count(i)
		print(i, k, '$', end='')


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

def dfs(root, level, path):
	if root.left is None and root.right is None:
		path[level] += 1
	if root.left:
		dfs(root.left, level + 1, path)
	if root.right:
		dfs(root.right, level + 1, path)

def pathCounts(root):
	h = height(root)
	path = {}
	for i in range(0, h + 1):
		path[i] = 0
	dfs(root, 1, path)
	for i in range(1, h + 1):
		if path[i]:
			print(i, path[i], end=' $')
	print()


def pathCounts(root):

	def func(node, arr, ans):
		if node == None:
			return
		if node.left == None and node.right == None:
			arr.append(node.data)
			ans.append(arr.copy())
			arr.pop()
			return 0
		arr.append(node.data)
		func(node.left, arr, ans)
		func(node.right, arr, ans)
		arr.pop()
	ans = []
	func(root, [], ans)
	d = {}
	for x in ans:
		if len(x) in d:
			d[len(x)] += 1
		else:
			d[len(x)] = 1
	ans = []
	for x in d:
		ans += [[x, d[x]]]
	for x in ans:
		print(x[0], x[1], '$', end='')
	print()


from collections import defaultdict

def pathCounts(root):
	store = defaultdict(lambda : 0)
	helper(root, 1, store)
	for (item, count) in sorted(store.items()):
		print(item, end=' ')
		print(count, end=' $')
	print()
	return

def helper(root, count, store):
	if not root:
		return
	if root.left == None and root.right == None:
		store[count] += 1
	helper(root.left, count + 1, store)
	helper(root.right, count + 1, store)
	return


def pathCounts(root):
	d = dict()
	D(d, root, 1)
	for i in d:
		print(i, d[i], end=' $')
	print()

def D(d, root, k):
	if root and (not root.left) and (not root.right):
		if k not in d:
			d[k] = 1
		else:
			d[k] += 1
	if root:
		D(d, root.left, k + 1)
		D(d, root.right, k + 1)


def pathCounts(root):

	def root_node(root, count):
		if root == None:
			return None
		count += 1
		if root.left == None and root.right == None:
			if count not in dict1:
				dict1[count] = 1
			else:
				dict1[count] += 1
		if root_node(root.left, count) or root_node(root.right, count):
			return True
		count -= 1
		return False
	string = ''
	dict1 = dict()
	root_node(root, 0)
	for i in dict1:
		string = string + str(i) + ' ' + str(dict1[i]) + ' ' + '$'
	print(string)


def pathCounts(root):
	l = []
	d = {}

	def helper(root):
		if root is None:
			return
		l.append(root.data)
		if not root.left and (not root.right):
			if len(l) not in d:
				d[len(l)] = 0
			d[len(l)] += 1
		helper(root.left)
		helper(root.right)
		l.pop()
	helper(root)
	for i in d:
		print(i, d[i], '$', end='')
	print()


def pathCounts(root):
	temp = 0
	global _list1
	_list1 = []
	if root.left:
		pathCountsUtil(root.left, temp + 1)
	if root.right:
		pathCountsUtil(root.right, temp + 1)
	s = set()
	for i in _list1:
		s.add(i)
	for i in s:
		print(str(i) + ' ' + str(_list1.count(i)) + ' $', end='')
	print()
s1 = set()

def pathCountsUtil(root, temp):
	global arr
	if root.left:
		pathCountsUtil(root.left, temp + 1)
	if root.right:
		pathCountsUtil(root.right, temp + 1)
	if not root.left and (not root.right):
		_list1.append(temp + 1)


def pathCounts(root):

	def traversal(root):
		nonlocal count
		if root == None:
			return None
		count += 1
		if root.left == None and root.right == None:
			if count not in dict1:
				dict1[count] = 1
			else:
				dict1[count] += 1
		if traversal(root.left) or traversal(root.right):
			return True
		count -= 1
		return False
	count = 0
	dict1 = dict()
	traversal(root)
	string = ''
	arrx = sorted(list(dict1.items()), key=lambda x: [0])
	for i in arrx:
		string += str(i[0]) + ' ' + str(i[1]) + ' $'
	print(string)


def pathCounts(root):

	def dfs(root, cnt):
		if root.left == None and root.right == None:
			cnt += 1
			hm[cnt] = 1 + hm.get(cnt, 0)
			return
		cnt += 1
		if root.left:
			dfs(root.left, cnt)
		if root.right:
			dfs(root.right, cnt)
	res = []
	hm = {}
	dfs(root, 0)
	for (k, v) in hm.items():
		res.append((k, v))
	res.sort()
	for item in res:
		(l, cnt) = item
		print(l, cnt, end=' $')
	print()


def pathCounts(root):
	d = {}
	x = []

	def helper(root):
		q = []
		level = 1
		if not root:
			return None
		q.append(root)
		while q:
			count = 0
			for i in range(len(q)):
				a = q.pop(0)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				if a.left == None and a.right == None:
					count += 1
			if count != 0:
				d[level] = count
			level += 1
	helper(root)
	ans = ''
	for i in d:
		ans += str(i) + ' '
		ans += str(d[i]) + ' ' + '$'
	print(ans)


def pathCounts(root):
	dic = dict()

	def rec(nod, dis):
		if nod.left is None and nod.right is None:
			if dis not in dic:
				dic[dis] = 0
			dic[dis] += 1
			return
		if nod.left:
			rec(nod.left, dis + 1)
		if nod.right:
			rec(nod.right, dis + 1)
	rec(root, 1)
	for i in sorted(dic.keys()):
		print(i, dic[i], '$', end='')
	print()


def pathCounts(root):
	l = []
	q = [[root, 1]]
	c = 0
	s = {}
	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])
		c += 1
		if f == 0:
			if g in s:
				s[g] += 1
			else:
				s[g] = 1
	b = []
	for i in s:
		b.append([i, s[i]])
	b.sort(key=lambda x: x[0])
	for i in b:
		print(i[0], i[1], end=' $')
	print()


def pathCounts(root):
	table = {}
	solve(root, 1, table)
	for k in sorted(table):
		print(k, end=' ')
		print(table[k], end=' $')
	print()

def solve(root, path_len, table):
	if not root:
		return
	if not root.left and (not root.right):
		table[path_len] = 1 + table.get(path_len, 0)
	solve(root.left, path_len + 1, table)
	solve(root.right, path_len + 1, table)


def pathCounts(root):
	final = {}

	def solve(root, ans):
		ans.append(root.data)
		if root.left == None and root.right == None:
			n = len(ans)
			if n in final:
				final[n] += 1
			else:
				final[n] = 1
		if root.left:
			solve(root.left, ans)
		if root.right:
			solve(root.right, ans)
		ans.pop()
	solve(root, [])
	d = ''
	for i in final.items():
		d += str(i[0])
		d += ' '
		d += str(i[1])
		d += ' '
		d += '$'
	print(d)


def pathCounts(root):

	def dfs(root, cnt):
		if root.left == None and root.right == None:
			cnt += 1
			res.append(cnt)
			return
		cnt += 1
		if root.left:
			dfs(root.left, cnt)
		if root.right:
			dfs(root.right, cnt)
	res = []
	dfs(root, 0)
	freq = {}
	for ele in res:
		freq[ele] = 1 + freq.get(ele, 0)
	out = []
	for (k, v) in freq.items():
		print(k, v, end=' $')
	print()
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		pathCounts(root)


def pathCounts(root):
	d = {}

	def cnt(r, l):
		if not (r.left or r.right):
			d[l] = d.get(l, 0) + 1
		for b in (r.left, r.right):
			if b:
				cnt(b, l + 1)
	cnt(root, 1)
	print(''.join([' '.join([str(k), str(d[k]), '$']) for k in sorted(d.keys())]))
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		pathCounts(root)


def pathCounts(root):
	ans = []

	def pa(root, s):
		if root is None:
			return
		if root.left == None and root.right == None:
			s.append(root.data)
			ans.append(s.copy())
			s.pop()
			return
		s.append(root.data)
		if root.left:
			pa(root.left, s)
		if root.right:
			pa(root.right, s)
		s.pop()
	pa(root, [])
	d = {}
	for i in ans:
		n = len(i)
		if n not in d:
			d[n] = 1
		else:
			d[n] += 1
	for k in sorted(d):
		print(k, d[k], end=' $')
	print()
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		pathCounts(root)


def asd(root, d, c):
	if root == None:
		return
	else:
		c += 1
		if root.left == None and root.right == None:
			if c in d.keys():
				d[c] += 1
			else:
				d[c] = 1
		asd(root.left, d, c)
		asd(root.right, d, c)

def pathCounts(root):
	c = 0
	d = {}
	asd(root, d, c)
	for i in sorted(d.keys()):
		print(i, end=' ')
		print(d[i], end=' ')
		print('$', end='')
	print()


def pathCounts(root):
	d = {}

	def f(root, pl, d):
		if root == None:
			return
		if root.left == None and root.right == None:
			d[pl] = d.get(pl, 0) + 1
			return
		f(root.left, pl + 1, d)
		f(root.right, pl + 1, d)
	f(root, 1, d)
	for i in sorted(d):
		print(i, d[i], '$', end='')
	print()


def pathCounts(root):
	lengthMap = dict()
	_pathCounts(root, lengthMap, [])
	for key in sorted(lengthMap.keys()):
		s = str(key) + ' ' + str(lengthMap[key]) + ' ' + '$'
		print(s, end='')
	print()

def _pathCounts(root, lengthMap, path):
	if not root:
		return
	path.append(root)
	if root.left is None and root.right is None:
		if len(path) in lengthMap:
			lengthMap[len(path)] += 1
		else:
			lengthMap[len(path)] = 1
	_pathCounts(root.left, lengthMap, path)
	_pathCounts(root.right, lengthMap, path)
	path.remove(root)


def path(root, count, l):
	if root == None:
		return
	if root.left == None and root.right == None:
		l.append(count)
		return
	path(root.left, count + 1, l)
	path(root.right, count + 1, l)

def pathCounts(root):
	l = []
	count = 1
	path(root, count, l)
	for i in set(l):
		print('{} {} '.format(i, l.count(i)), end='$')
	print()


from collections import defaultdict

def pathCounts(root):
	if root is None:
		return root
	Dict = defaultdict(int)

	def solve(root, lvl):
		if root is None:
			return
		if root.left is None and root.right is None:
			Dict[lvl] += 1
			return
		solve(root.left, lvl + 1)
		solve(root.right, lvl + 1)
	solve(root, 1)
	for i in Dict:
		print(i, Dict[i], end=' $')
	print()


from collections import deque

def pathCounts(root):
	q = deque()
	q.append(root)
	ans = []
	path_length = 0
	while q:
		path_length += 1
		count = 0
		for _ in range(len(q)):
			node = q.popleft()
			if not node.left and (not node.right):
				count += 1
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if count != 0:
			print(path_length, count, end=' $')
	print('')


from collections import defaultdict

def pathCounts(root):
	d = defaultdict(int)

	def helper(root, height):
		if root is None:
			return
		if root.left is None and root.right is None:
			d[height] += 1
			return
		helper(root.left, height + 1)
		helper(root.right, height + 1)
	helper(root, 1)
	for i in d:
		print(i, d[i], end=' $')
	print()


def pathCounts(root):
	ans = {}

	def util(root, level):
		nonlocal ans
		if root is None:
			return
		if root.left is None and root.right is None:
			ans[level] = ans.get(level, 0) + 1
			return
		util(root.left, level + 1)
		util(root.right, level + 1)
	util(root, 1)
	s = ''
	for (i, j) in ans.items():
		s = s + str(i) + ' ' + str(j) + ' ' + '$'
	print(s)


from collections import defaultdict

def pathCounts(root):
	res = defaultdict(lambda : 0)

	def helper(root, depth):
		if root is None:
			return
		if root.left is None and root.right is None:
			res[depth] += 1
			return
		helper(root.left, depth + 1)
		helper(root.right, depth + 1)
	helper(root, 1)
	k = sorted(res.items())
	ans = ''
	dollar = '$'
	for (depth, count) in k:
		n = '{} {} {}'.format(depth, count, dollar)
		ans += n
	print(ans)


def recur(root, level, d):
	if not root:
		return
	if not root.left and (not root.right):
		if level in d:
			d[level] += 1
		else:
			d[level] = 1
	recur(root.left, level + 1, d)
	recur(root.right, level + 1, d)

def pathCounts(root):
	d = {}
	recur(root, 1, d)
	for i in sorted(d):
		print(str(i) + ' ' + str(d[i]) + ' $', end='')
	print()


from collections import defaultdict

def recursive_counter(heights, curHeight, root):
	if root is None:
		return None
	if root.left is None and root.right is None:
		heights[curHeight] += 1
		return
	recursive_counter(heights, curHeight + 1, root.left)
	recursive_counter(heights, curHeight + 1, root.right)

def pathCounts(root):
	heights = defaultdict(int)
	recursive_counter(heights, 1, root)
	for i in heights:
		print(i, heights[i], end=' $')
	print()


def fn(root, dic, lvl):
	if root:
		if not root.left and (not root.right):
			try:
				dic[lvl] += 1
			except:
				dic[lvl] = 1
		fn(root.left, dic, lvl + 1)
		fn(root.right, dic, lvl + 1)

def pathCounts(root):
	dic = {}
	s = ''
	fn(root, dic, 1)
	for i in dic:
		s += str(i) + ' ' + str(dic[i]) + ' ' + '$'
	print(s)


table = dict()

def solve(node, c=0):
	c += 1
	if node == None:
		return
	if node.left == None and node.right == None:
		if c not in table:
			table[c] = 0
		table[c] += 1
		return
	solve(node.left, c)
	solve(node.right, c)
	return

def pathCounts(root):
	global table
	table = dict()
	solve(root)
	s = ''
	for key in table:
		s += str(key) + ' ' + str(table[key]) + ' ' + '$'
	print(s)


def freq(arr, val):
	return sum([1 for u in arr if u == val])

def helper(r, D, l):
	if r.right is None and r.left is None:
		D = D + [l]
		return D
	elif r.right is None and r.left is not None:
		return helper(r.left, D, l + 1)
	elif r.right is not None and r.left is None:
		return helper(r.right, D, l + 1)
	else:
		p1 = helper(r.left, D, l + 1)
		p2 = helper(r.right, D, l + 1)
		return p1 + p2

def pathCounts(r):
	res = helper(r, [], 1)
	L = set(res)
	s = ''
	for u in L:
		s = s + str(u) + ' ' + str(freq(res, u)) + ' $'
	print(s)


def pathCounts(root):
	if root is None:
		return '0 0 $'
	queue = [root]
	path_lengths = {}
	length = 1
	while queue:
		n = len(queue)
		for i in range(len(queue)):
			node = queue.pop(0)
			if node.left is None and node.right is None:
				if length not in path_lengths:
					path_lengths[length] = 1
				else:
					path_lengths[length] += 1
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		length += 1
	P = list(path_lengths.items())
	P.sort(key=lambda x: x[0])
	result = ''
	for (a, b) in P:
		result += str(a) + ' ' + str(b) + ' $'
	print(result)


def solve(root, ans, level):
	if root == None:
		return
	if root.left == None and root.right == None:
		ans.append(level)
	solve(root.left, ans, level + 1)
	solve(root.right, ans, level + 1)

def pathCounts(root):
	ans = []
	solve(root, ans, 1)
	ans.sort()
	count = 1
	for i in range(1, len(ans)):
		if ans[i] > ans[i - 1]:
			print(ans[i - 1], count, end=' $')
			count = 0
		count += 1
	print(ans[-1], count, end=' $')
	print()


def dfs(root, curr, hashmap):
	if not root:
		return
	curr += 1
	if root.left == None and root.right == None:
		if curr not in hashmap:
			hashmap[curr] = 0
		hashmap[curr] += 1
		return
	dfs(root.left, curr, hashmap)
	dfs(root.right, curr, hashmap)

def pathCounts(root):
	hashmap = {}
	dfs(root, 0, hashmap)
	ans = []
	for path in hashmap:
		ans.append(str(path) + ' ' + str(hashmap[path]))
	ans = ' $'.join(ans)
	ans += ' $'
	print(ans)


def pathCounts(root):
	l = get(root)
	d = {}
	for item in l:
		if item in d:
			d[item] += 1
		else:
			d[item] = 1
	for item in d:
		print(item, d[item], '$', end='')
	print()

def get(root):
	if root:
		if root.left == None and root.right == None:
			return [1]
		else:
			a = get(root.left)
			a.extend(get(root.right))
			for i in range(len(a)):
				a[i] += 1
			return a
	else:
		return []


def paths(dic, root, l):
	if root:
		if root.left == None and root.right == None:
			if l in dic:
				dic[l] += 1
			else:
				dic[l] = 1
		paths(dic, root.left, l + 1)
		paths(dic, root.right, l + 1)

def pathCounts(root):
	dic = {}
	paths(dic, root, 1)
	x = ''
	for i in sorted(dic):
		st = str(i) + ' ' + str(dic[i]) + ' $'
		x += st
	print(x)


def pathCounts(root):
	d = {}

	def sol(r, cur):
		nonlocal d
		if r == None:
			return
		if r.left == None and r.right == None:
			cur += 1
			if cur in d:
				d[cur] += 1
			else:
				d[cur] = 1
			return
		sol(r.left, cur + 1)
		sol(r.right, cur + 1)
	sol(root, 0)
	ans = []
	for i in sorted(d.keys()):
		print(i, d[i], '$', end='')
	print()


def helper(root, d, l):
	if root == None:
		return
	if root.left == None and root.right == None:
		if l in d:
			d[l] = d[l] + 1
		else:
			d[l] = 1
	helper(root.left, d, l + 1)
	helper(root.right, d, l + 1)

def pathCounts(root):
	d = {}
	helper(root, d, 1)
	for l in sorted(d):
		print(l, d[l], '$', end='')
	print()
	del d


def helper(root, d, count_dict):
	if root is None:
		return
	if root.left is None and root.right is None:
		count_dict.setdefault(d + 1, 0)
		count_dict[d + 1] += 1
		return
	helper(root.left, d + 1, count_dict)
	helper(root.right, d + 1, count_dict)

def pathCounts(root):
	count_dict = {}
	helper(root, 0, count_dict)
	counts = list(sorted(list(count_dict.keys())))
	tmp_string = ''
	for key in counts:
		tmp_string += str(key) + ' ' + str(count_dict[key]) + ' $'
	print(tmp_string)


def pathCounts(root):

	def count(root, ans, path):
		if not root:
			return ans
		if not root.left and (not root.right):
			ans[path] = ans.get(path, 0) + 1
			return ans
		count(root.left, ans, path + 1)
		count(root.right, ans, path + 1)
		return ans
	d = count(root, {}, 1)
	s = ''
	for x in d:
		s += '{} {} $'.format(x, d[x])
	print(s)


def pathCounts(root):
	paths = {}
	count = 0

	def traverse(root):
		nonlocal count
		if root == None:
			return
		count += 1
		if root.left == root.right == None:
			if paths.get(count) == None:
				paths[count] = 1
			else:
				paths[count] += 1
		traverse(root.left)
		traverse(root.right)
		count -= 1
	traverse(root)
	for i in sorted(paths.keys()):
		print(i, paths[i], end=' $')
	print()
	return


def path(dic, root, level):
	if root:
		if root.left is None and root.right is None:
			if level in dic:
				dic[level] += 1
			else:
				dic[level] = 1
		path(dic, root.left, level + 1)
		path(dic, root.right, level + 1)

def pathCounts(root):
	dic = {}
	path(dic, root, 1)
	x = ''
	for i in sorted(dic):
		st = str(i) + ' ' + str(dic[i]) + ' $'
		x += st
	print(x)


def pathCounts(root):
	res = {}
	traverse(root, 1, res)
	for length in res:
		print('{} {} $'.format(length, res[length]), end='')
	print()

def traverse(cur, length, res):
	if not cur:
		return
	if not cur.left and (not cur.right):
		if length not in res:
			res[length] = 1
		else:
			res[length] += 1
	traverse(cur.left, length + 1, res)
	traverse(cur.right, length + 1, res)


import collections

def pathCounts(root):
	d = collections.defaultdict(int)

	def solve(root, height):
		if root == None:
			return None
		if not root.left and (not root.right):
			d[height] += 1
			return
		solve(root.left, height + 1)
		solve(root.right, height + 1)
	solve(root, 1)
	for i in d:
		print(i, d[i], end=' $')
	print()