Given a binary tree and an integer value K, the task is to find all nodes data in the given binary tree having exactly K leaves in sub-tree rooted with them.
NOTE: Nodes should be printed in the order in which they appear in postorder traversal.
Example 1:
Input:
K = 1
      0
    /   \
   1     2
Output: -1
Explanation: There is no node in this
tree which has one leaf in the sub tree
below it.
Example 2:
Input:
K = 2
          0
        /   \
       1     2
           /  
          4
        /   \
       5     9
Output: 4 2
Explanation: Nodes with data 2 and 4, have
2 leaves in the subtree below it.
Your Task:
Just complete the function btWithKleaves() and returns the answer (as a vector in CPP, as an ArrayList in java, and as list in python)
Note: If no node is found the list returned should contain only one value -1.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= N <= 1000
1 <= K <= 1000
1 <= value of nodes <= 10000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    # Your task is to complete this function

    # function should print the node whose subtrees has exactly k leaves 

    # if no such leaves is present print -1    

    def btWithKleaves(self, root, k):

        # Code here

Solutions:
class Solution:

	def helper(self, node, k):
		if node is None:
			return 0
		if not node.left and (not node.right):
			return 1
		(l, r) = (self.helper(node.left, k), self.helper(node.right, k))
		if l + r == k:
			self.res.append(node.data)
		return l + r

	def btWithKleaves(self, root, k):
		self.res = []
		self.helper(root, k)
		if self.res == []:
			return [-1]
		return self.res


class Solution:

	def util(self, root, k):
		global ans
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		l = self.util(root.left, k)
		r = self.util(root.right, k)
		if l + r == k:
			ans.append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		global ans
		ans = []
		self.util(root, k)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def solve(self, root, k):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		l = self.solve(root.left, k)
		r = self.solve(root.right, k)
		if l + r == k:
			self.res.append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		self.res = []
		self.solve(root, k)
		if self.res == []:
			return [-1]
		return self.res


class Solution:

	def btWithKleaves(self, root, k):
		temp = set()

		def find(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			total = find(root.right) + find(root.left)
			if total == k:
				temp.add(root)
			return total
		out = []

		def traverse(root):
			if not root:
				return
			traverse(root.left)
			traverse(root.right)
			if root in temp:
				out.append(root.data)
		find(root)
		traverse(root)
		return [-1] if out == [] else out


class Solution:

	def solve(self, node, k):
		if not node:
			return 0
		if node and (not node.left) and (not node.right):
			return 1
		leaves = self.solve(node.left, k) + self.solve(node.right, k)
		if leaves == k:
			self.ans.append(node.data)
		return leaves

	def btWithKleaves(self, root, k):
		self.ans = []
		self.solve(root, k)
		return self.ans if len(self.ans) else [-1]


flag = True

class Solution:

	def btWithKleavesUtil(self, root, k, nodes):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		total = self.btWithKleavesUtil(root.left, k, nodes) + self.btWithKleavesUtil(root.right, k, nodes)
		if total == k:
			nodes.append(root.data)
			global flag
			flag = False
		return total

	def btWithKleaves(self, root, k):
		global flag
		flag = True
		nodes = []
		self.btWithKleavesUtil(root, k, nodes)
		if flag:
			nodes = []
			nodes.append(-1)
		return nodes


class Solution:

	def btWithKleaves(self, root, k):
		stack = [root]
		parent = {}
		parent[root] = Node(0)
		leaves = {}
		leaves[root] = 0
		vis = set()
		stack = [root]
		while stack:
			top = stack.pop(0)
			if not top.left and (not top.right):
				leaves[top] = 1
			else:
				leaves[top] = 0
			if top.left:
				stack.append(top.left)
			if top.right:
				stack.append(top.right)
		stack = [root]
		res = []
		while stack:
			top = stack[-1]
			if top.left and top.left not in vis:
				stack.append(top.left)
				vis.add(top.left)
			elif top.right and top.right not in vis:
				stack.append(top.right)
				vis.add(top.right)
			else:
				node = stack.pop()
				if node.left:
					leaves[node] += leaves[node.left]
				if node.right:
					leaves[node] += leaves[node.right]
				if leaves[node] == k and (node.left or node.right):
					res.append(node.data)
		if res == []:
			return [-1]
		return res


class Solution:

	def Postorder(self, root, k, count):
		if root == None:
			return 0
		l = self.Postorder(root.left, k, count)
		r = self.Postorder(root.right, k, count)
		if root.left == None and root.right == None:
			return 1
		if l + r == k:
			count[0].append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		count = [[]]
		self.Postorder(root, k, count)
		if len(count[0]) == 0:
			return [-1]
		return count[0]


class Solution:

	def solve(self, root, k, res):
		if root.left is None and root.right is None:
			return 1
		(right_leaves, left_leaves) = (0, 0)
		if root.left:
			left_leaves = self.solve(root.left, k, res)
		if root.right:
			right_leaves = self.solve(root.right, k, res)
		leaves = right_leaves + left_leaves
		if leaves == k:
			res.append(root.data)
		return leaves

	def btWithKleaves(self, root, k):
		res = []
		_ = self.solve(root, k, res)
		if res:
			return res
		return [-1]


class Solution:

	def btWithKleaves(self, root, k):

		def func(root, k, ans):
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return 1
			left = func(root.left, k, ans)
			right = func(root.right, k, ans)
			if left + right == k:
				ans.append(root.data)
			return left + right
		ans = []
		func(root, k, ans)
		if ans:
			return ans
		return [-1]


class Solution:

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

		def recursive(root, k):
			nonlocal ans
			if root is None:
				return 0
			if not root.left and (not root.right):
				return 1
			left = recursive(root.left, k)
			right = recursive(root.right, k)
			if left + right == k:
				ans.append(root.data)
			return left + right
		recursive(root, k)
		return ans if ans else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		output = []
		self.helper(root, k, output)
		return output if output else [-1]

	def helper(self, root, target, store):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		left = self.helper(root.left, target, store)
		right = self.helper(root.right, target, store)
		if left + right == target:
			store.append(root.data)
		return left + right


class Solution:

	def btWithKleaves(self, root, k):
		result = []

		def traverse(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			left_count = traverse(root.left)
			right_count = traverse(root.right)
			if left_count + right_count == k:
				result.append(root.data)
			return left_count + right_count
		traverse(root)
		return result if result else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		if not root:
			return
		ans = []

		def dfs(node, k):
			if not node:
				return 0
			l = dfs(node.left, k)
			r = dfs(node.right, k)
			if not node.left and (not node.right):
				return 1
			if l + r == k:
				ans.append(node.data)
			return l + r
		dfs(root, k)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

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

		def traversal(root, k):
			nonlocal ans
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return 1
			ls = traversal(root.left, k)
			rs = traversal(root.right, k)
			if ls + rs == k:
				ans.append(root.data)
			return ls + rs
		traversal(root, k)
		return ans if len(ans) > 0 else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		arr = []
		self.value(root, k, arr)
		if not arr:
			arr = arr + [-1]
		return arr

	def value(self, root, k, arr):
		if root.left:
			a = self.value(root.left, k, arr)
		else:
			a = 0
		if root.right:
			b = self.value(root.right, k, arr)
		else:
			b = 0
		val = 0
		if a == 0 and b == 0:
			val = 1
			return val
		val = a + b
		if val == k:
			arr.append(root.data)
		return val


class Solution:

	def btWithKleaves(self, root, k):
		ans = []
		self.util(root, ans, k)
		if not ans:
			return [-1]
		return ans

	def util(self, root, ans, k):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		left = self.util(root.left, ans, k)
		right = self.util(root.right, ans, k)
		total_leaves = left + right
		if total_leaves == k:
			ans.append(root.data)
		return total_leaves


class Solution:

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

		def rec(nod, k):
			if nod is None:
				return 0
			if nod.left is None and nod.right is None:
				return 1
			l = rec(nod.left, k)
			r = rec(nod.right, k)
			if l + r == k:
				ans.append(nod.data)
			return l + r
		rec(root, k)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def btWithKleaves(self, root, k):
		if root is None:
			return None
		result = []
		self.btWithKleavesUtil(root, result, k)
		if len(result) == 0:
			result.append(-1)
		return result

	def btWithKleavesUtil(self, root, result, k):
		if root is None:
			return 0
		if root and root.left is None and (root.right is None):
			return 1
		lstlnc = self.btWithKleavesUtil(root.left, result, k)
		rstlnc = self.btWithKleavesUtil(root.right, result, k)
		if lstlnc + rstlnc == k:
			result.append(root.data)
		return lstlnc + rstlnc


class Solution:

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

		def helper(root, k):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			l = helper(root.left, k)
			r = helper(root.right, k)
			if l + r == k:
				ans.append(root.data)
			return l + r
		helper(root, k)
		if ans:
			return ans
		return [-1]


class Solution:

	def btWithKleaves(self, root, k):

		def f(node, ans):
			if not node.left and (not node.right):
				return 1
			l = 0
			r = 0
			if node.left:
				l = f(node.left, ans)
			if node.right:
				r = f(node.right, ans)
			if l + r == k:
				ans += [node.data]
			return l + r
		ans = []
		f(root, ans)
		if not ans:
			return [-1]
		return ans


class Solution:

	def btWithKleaves(self, root, k):

		def _solve(nd):
			if not nd:
				return 0
			L = _solve(nd.left)
			R = _solve(nd.right)
			V = L + R
			if V > 0 and V == k:
				ans.append(nd.data)
			return V if V > 0 else 1
		ans = []
		_solve(root)
		return ans if ans else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		nodes = []

		def rec(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			res = rec(root.left) + rec(root.right)
			if res == k:
				nodes.append(root.data)
			return res
		rec(root)
		return nodes if nodes else [-1]


class Solution:

	def ino(self, r, k, l):
		if r is None:
			return 0
		if r.left is None and r.right is None:
			return 1
		a = self.ino(r.left, k, l)
		b = self.ino(r.right, k, l)
		if a + b == k:
			l.append(r.data)
		return a + b

	def btWithKleaves(self, root, k):
		l = []
		self.ino(root, k, l)
		if l == []:
			return [-1]
		return l


class Solution:

	def btWithKleaves(self, root, k):
		res = []

		def helper(root):
			nonlocal res
			if not root.left and (not root.right):
				return 1
			if root.left:
				ls = helper(root.left)
			else:
				ls = 0
			if root.right:
				rs = helper(root.right)
			else:
				rs = 0
			if ls + rs == k:
				res.append(root.data)
			return ls + rs
		helper(root)
		return res if len(res) > 0 else [-1]


class Solution:

	def btWithKleaves(self, root, k):

		def ktree(ptr, k, res):
			if not ptr:
				return 0
			if ptr.left is None and (not ptr.right):
				return 1
			total = ktree(ptr.left, k, res) + ktree(ptr.right, k, res)
			if total == k:
				res.append(ptr.data)
			return total
		res = []
		ktree(root, k, res)
		if res == []:
			return [-1]
		return res


class Solution:

	def btWithKleaves(self, root, k):
		answer = []

		def solve(root):
			if root:
				nonlocal answer
				if not root.left and (not root.right):
					return 1
				ans = solve(root.left) + solve(root.right)
				if ans == k:
					answer.append(root.data)
				return ans
			return 0
		solve(root)
		if len(answer) == 0:
			return [-1]
		return answer


from collections import *

class Solution:

	def isLeaf(self, node):
		return not node.left and (not node.right)

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

		def solve(node):
			if self.isLeaf(node):
				return 1
			(l, r) = (0, 0)
			if node.left:
				l = solve(node.left)
			if node.right:
				r = solve(node.right)
			temp = l + r + int(self.isLeaf(node))
			if temp == k:
				ans.append(node.data)
			return temp
		solve(root)
		return ans if ans else [-1]


class Solution:

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

		def solve(root, k):
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return 1
			global ans
			leaf = solve(root.left, k)
			leaf += solve(root.right, k)
			if leaf == k:
				ans.append(root.data)
			return leaf
		solve(root, k)
		if len(ans) == 0:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(50000)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = 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

class Solution:

	def btWithKleaves(self, root, k):
		res = []
		self.helper(root, k, res)
		if res == []:
			return [-1]
		else:
			return res

	def helper(self, root, k, res):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		count = self.helper(root.left, k, res) + self.helper(root.right, k, res)
		if count == k:
			res.append(root.data)
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		k = int(input())
		s = input()
		root = buildTree(s)
		nodes = Solution().btWithKleaves(root, k)
		for node in nodes:
			print(node, end=' ')
		print()


class Solution:

	def btw(self, root, k, arr):
		if root == None:
			return (0, 0, [])
		if not root.left and (not root.right):
			return (1, 0, [])
		a = self.btw(root.left, k, arr)
		b = self.btw(root.right, k, arr)
		if a[0] + b[0] == k:
			ar = a[2] + b[2] + [root.data]
			c = a[1] + b[1] + 1
		else:
			c = a[1] + b[1]
			ar = a[2] + b[2]
		d = a[0] + b[0]
		return (d, c, ar)

	def btWithKleaves(self, root, k):
		arr = self.btw(root, k, [])[2]
		if arr:
			return arr
		return [-1]


class Solution:

	def kLeavesUtil(self, root, k, ans):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		lLeaves = self.kLeavesUtil(root.left, k, ans)
		rLeaves = self.kLeavesUtil(root.right, k, ans)
		if lLeaves + rLeaves == k:
			ans.append(root.data)
		return lLeaves + rLeaves

	def btWithKleaves(self, root, k):
		ans = []
		self.kLeavesUtil(root, k, ans)
		if len(ans) == 0:
			return [-1]
		else:
			return ans


class Solution:

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

	def solve(self, root, k):
		if root is None:
			return 0
		if not root.left and (not root.right):
			return 1
		c = self.solve(root.left, k) + self.solve(root.right, k)
		if c == k:
			self.ans.append(root.data)
		return c

	def btWithKleaves(self, root, k):
		self.solve(root, k)
		if len(self.ans) == 0:
			self.ans.append(-1)
		return self.ans


import sys
sys.setrecursionlimit(1001)

class Solution:

	def btWithKleaves(self, root, k):
		res = []
		self.helper(root, res, k)
		if len(res):
			return res
		else:
			return [-1]

	def helper(self, root, res, k):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		count = self.helper(root.left, res, k) + self.helper(root.right, res, k)
		if count == k:
			res.append(root.data)
		return count


class Solution:

	def btWithKleaves(self, root, k):

		def postorder(root):
			if root.left == None and root.right == None:
				return 1
			left = right = 0
			if root.left:
				left = postorder(root.left)
			if root.right:
				right = postorder(root.right)
			if left + right == k:
				ans.append(root.data)
			return left + right
		ans = []
		postorder(root)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def isleaf(self, root):
		return root.left == None and root.right == None

	def traversal(self, root, ans, k):
		if root == None:
			return 0
		if self.isleaf(root):
			return 1
		l = self.traversal(root.left, ans, k)
		r = self.traversal(root.right, ans, k)
		node = l + r
		if node == k:
			ans.append(root.data)
		return node

	def btWithKleaves(self, root, k):
		ans = []
		self.traversal(root, ans, k)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def btWithKleaves(self, root, k):

		def dfs(root):
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return 1
			a = dfs(root.left)
			b = dfs(root.right)
			if a + b == k:
				c.append(root.data)
			return a + b
		c = []
		dfs(root)
		if len(c) == 0:
			return [-1]
		return c


class Solution:

	def btWithKleaves(self, root, k):
		nodes = []
		self.nodesWithKLeaves(root, nodes, k)
		return nodes if nodes else [-1]

	def nodesWithKLeaves(self, root, nodes, k):
		if not root:
			return 0
		if root.left is None and root.right is None:
			return 1
		left = self.nodesWithKLeaves(root.left, nodes, k)
		right = self.nodesWithKLeaves(root.right, nodes, k)
		if left + right == k:
			nodes.append(root.data)
		return left + right


class Solution:

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

		def leaves(root):
			if not root:
				return 0
			elif not root.left and (not root.right):
				return 1
			else:
				l = leaves(root.left)
				r = leaves(root.right)
				total = l + r
				if total == k:
					ans.append(root.data)
				return total
		leaves(root)
		if ans:
			return ans
		else:
			return [-1]


class Solution:

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

		def util(root):
			nonlocal ans
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return 1
			l = util(root.left)
			r = util(root.right)
			if l + r == k:
				ans.append(root.data)
			return l + r
		util(root)
		return [-1] if len(ans) == 0 else ans


class Solution:

	def isleaf(self, root):
		if not root:
			return False
		if not root.left and (not root.right):
			return True
		return False

	def solve(self, root, k, res):
		if not root:
			return 0
		if self.isleaf(root):
			return 1
		left = self.solve(root.left, k, res)
		right = self.solve(root.right, k, res)
		if k == left + right:
			res.append(root.data)
		return left + right

	def btWithKleaves(self, root, k):
		res = []
		c = 0
		self.solve(root, k, res)
		if res == []:
			return [-1]
		return res


class Solution:

	def btWithKleaves(self, root, k):

		def solve(root, k, ans):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			a = solve(root.left, k, ans)
			b = solve(root.right, k, ans)
			if k == a + b:
				ans.append(root.data)
			return a + b
		ans = []
		solve(root, k, ans)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def count_leaves(self, root, k):
		global ans
		if not root:
			return 0
		if not root.right and (not root.left):
			return 1
		l = self.count_leaves(root.left, k)
		r = self.count_leaves(root.right, k)
		if l + r == k:
			ans.append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		global ans
		ans = []
		self.count_leaves(root, k)
		return ans if ans else [-1]


class Solution:

	def kleaves(self, root, k, res):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		totalleaves = self.kleaves(root.left, k, res) + self.kleaves(root.right, k, res)
		if k == totalleaves:
			res.append(root.data)
		return totalleaves

	def btWithKleaves(self, root, k):
		res = []
		self.kleaves(root, k, res)
		if len(res) == 0:
			res.append(-1)
		return res


class Solution:

	def traversal(self, root, mp):
		if not root:
			return 0
		l = self.traversal(root.left, mp)
		r = self.traversal(root.right, mp)
		if root.left is None and root.right is None:
			return 1
		else:
			val = l + r
			if val in mp:
				mp[val].append(root.data)
			else:
				mp[val] = [root.data]
			return val

	def btWithKleaves(self, root, k):
		mp = {}
		self.traversal(root, mp)
		return mp[k] if k in mp else [-1]


class Solution:

	def helper(self, root, k, ans):
		if not root:
			return 0
		le = self.helper(root.left, k, ans)
		ri = self.helper(root.right, k, ans)
		if le + ri == k:
			ans.append(root.data)
		if root.left:
			return le + ri
		if root.right:
			return le + ri
		else:
			return 1

	def btWithKleaves(self, root, k):
		if not root:
			return 0
		ans = []
		self.helper(root, k, ans)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

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

	def calculate_node(self, root, k):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		left = self.calculate_node(root.left, k)
		right = self.calculate_node(root.right, k)
		if left + right == k:
			self.result.append(root.data)
		return left + right

	def btWithKleaves(self, root, k):
		self.calculate_node(root, k)
		return self.result if self.result else [-1]


class Solution:

	def util(self, root, k, res):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		l = self.util(root.left, k, res)
		r = self.util(root.right, k, res)
		if l + r == k:
			res.append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		res = []
		self.util(root, k, res)
		if len(res) == 0:
			return [-1]
		return res


class Solution:

	def isleaf(self, root):
		return root.left is None and root.right is None

	def helper(self, root, res, k):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		l = self.helper(root.left, res, k) + self.helper(root.right, res, k)
		if l == k:
			res.append(root.data)
		return l

	def btWithKleaves(self, root, k):
		res = []
		self.helper(root, res, k)
		return res if res else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		if root == None:
			return [-1]
		if root.left == None and root.right == None:
			return [-1]
		ans = []
		self.btWithKleavesUtil(root, k, ans)
		if not ans:
			return [-1]
		return ans

	def btWithKleavesUtil(self, root, k, ans):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		total = self.btWithKleavesUtil(root.left, k, ans) + self.btWithKleavesUtil(root.right, k, ans)
		if total == k:
			ans.append(root.data)
		return total


class Solution:

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

		def post(root, k):
			nonlocal ans
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			l = post(root.left, k)
			r = post(root.right, k)
			if l + r == k:
				ans.append(root.data)
			return l + r
		post(root, k)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def btWithKleaves(self, root, k):
		lis = []
		self.btWithKleavesUtil(root, k, lis)
		if len(lis) == 0:
			lis.append(-1)
		return lis

	def btWithKleavesUtil(self, root, k, result):
		if root is None:
			return 0
		lnc = self.btWithKleavesUtil(root.left, k, result)
		if root is not None and root.left is None and (root.right is None):
			return 1
		rnc = self.btWithKleavesUtil(root.right, k, result)
		if lnc + rnc == k:
			result.append(root.data)
		return lnc + rnc


class Solution:

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

		def helper(node, k):
			if node is None:
				return 0
			x = helper(node.left, k)
			y = helper(node.right, k)
			if x + y == k:
				self.ans.append(node.data)
			if node.left is None and node.right is None:
				return 1
			return x + y
		helper(root, k)
		return self.ans if self.ans else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		nodes = []
		self.solve(root, k, nodes)
		if not nodes:
			return [-1]
		return nodes

	def solve(self, root, k, nodes):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		ans = self.solve(root.left, k, nodes) + self.solve(root.right, k, nodes)
		if ans == k:
			nodes.append(root.data)
		return ans


class Solution:

	def solve(self, root, k, ans):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		total = self.solve(root.left, k, ans) + self.solve(root.right, k, ans)
		if k == total:
			ans.append(root.data)
		return total

	def btWithKleaves(self, root, k):
		ans = []
		count = self.solve(root, k, ans)
		if ans:
			return ans
		else:
			return [-1]


class Solution:

	def btWithKleaves(self, root, k):
		res = []

		def traverse(node, k):
			nonlocal res
			if node == None:
				return 0
			if node.left == None and node.right == None:
				return 1
			leaves = traverse(node.left, k) + traverse(node.right, k)
			if leaves == k:
				res.append(node.data)
			return leaves
		traverse(root, k)
		return res if len(res) > 0 else [-1]


class Solution:

	def getLeaves(self, root, k, nodes):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		leaves = self.getLeaves(root.left, k, nodes) + self.getLeaves(root.right, k, nodes)
		if leaves == k:
			nodes.append(root.data)
		return leaves

	def btWithKleaves(self, root, k):
		nodes = []
		self.getLeaves(root, k, nodes)
		if len(nodes) == 0:
			nodes.append(-1)
		return nodes


class Solution:

	def checkUtil(self, root, k, ans):
		if root == None:
			return 0
		p = self.checkUtil(root.left, k, ans)
		q = self.checkUtil(root.right, k, ans)
		if p + q == k:
			ans.append(root.data)
		if root.left == None and root.right == None:
			return p + q + 1
		return p + q

	def btWithKleaves(self, root, k):
		ans = []
		p = self.checkUtil(root, k, ans)
		if len(ans) == 0:
			ans.append(-1)
		return ans


class Solution:

	def util(self, node, k, l):
		if not node:
			return 0
		if node.left == None and node.right == None:
			return 1
		total = self.util(node.left, k, l) + self.util(node.right, k, l)
		if total == k:
			l.append(node.data)
		return total

	def btWithKleaves(self, root, k):
		l = []
		self.util(root, k, l)
		if len(l) == 0:
			return [-1]
		return l


class Solution:
	cnt = []

	def rec(self, root, k):
		if root == None:
			return 0
		l = self.rec(root.left, k)
		r = self.rec(root.right, k)
		if l + r == k:
			self.cnt.append(root.data)
		if root.left == None and root.right == None:
			return 1
		return l + r

	def btWithKleaves(self, root, k):
		self.cnt = []
		self.rec(root, k)
		if self.cnt == []:
			return [-1]
		return self.cnt


def rec(node, l, k):
	if node == None:
		return 0
	if node.left == None and node.right == None:
		return 1
	left = rec(node.left, l, k)
	right = rec(node.right, l, k)
	if left + right == k:
		l.append(node.data)
	return left + right

class Solution:

	def btWithKleaves(self, root, k):
		l = []
		rec(root, l, k)
		return l if len(l) > 0 else [-1]


class Solution:

	def btWithKleaves(self, root, k):
		ans = []
		count = self.btWithKleave(root, k, ans)
		if not ans:
			ans.append(-1)
		return ans

	def btWithKleave(self, root, k, ans):
		if root:
			if root.left == None and root.right == None:
				return 1
			else:
				count = self.btWithKleave(root.left, k, ans) + self.btWithKleave(root.right, k, ans)
				if count == k:
					ans.append(root.data)
				return count
		else:
			return 0


class Solution:

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

		def sol(r, k):
			nonlocal ans
			if r == None:
				return 0
			if r.left:
				l = 1
			else:
				l = 0
			if r.right:
				ri = 1
			else:
				ri = 0
			lev = max(l, sol(r.left, k)) + max(ri, sol(r.right, k))
			if lev == k:
				ans.append(r.data)
			return lev
		sol(root, k)
		if ans:
			return ans
		return [-1]


class Solution:

	def btWithKleaves(self, root, k):
		res = []
		self.traverse(root, k, res)
		return res if res else [-1]

	def traverse(self, cur, k, res):
		if not cur:
			return 0
		if not cur.left and (not cur.right):
			return 1
		left = self.traverse(cur.left, k, res)
		right = self.traverse(cur.right, k, res)
		if left + right == k:
			res.append(cur.data)
		return left + right


class Solution:

	def count(self, root, k):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		left = self.count(root.left, k)
		right = self.count(root.right, k)
		if left + right == k:
			global result
			result.append(root.data)
		return left + right

	def btWithKleaves(self, root, k):
		global result
		result = []
		self.count(root, k)
		if len(result) == 0:
			return [-1]
		else:
			return result


def solve(root, k, cur, ans):
	if root == None:
		return (ans, cur)
	elif root.left == None and root.right == None:
		return (ans, cur + 1)
	else:
		t1 = solve(root.left, k, cur, ans)
		t2 = solve(root.right, k, cur, ans)
		if t1[1] + t2[1] == k:
			ans.append(root.data)
		return (ans, t1[1] + t2[1])

class Solution:

	def btWithKleaves(self, root, k):
		ans1 = solve(root, k, cur=0, ans=[])
		ans = ans1[0]
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def btWithKleaves(self, root, k):
		self.output = []

		def nodeFinder(root, k):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return 1
			lefty = nodeFinder(root.left, k)
			righty = nodeFinder(root.right, k)
			if lefty + righty == k:
				self.output.append(root.data)
			return lefty + righty
		nodeFinder(root, k)
		return [-1] if len(self.output) == 0 else self.output


class Solution:

	def kp(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		tot = self.kp(root.left) + self.kp(root.right)
		if tot == self.k:
			self.out.append(root.data)
		return tot

	def btWithKleaves(self, root, k):
		self.k = k
		self.out = []
		self.kp(root)
		if len(self.out) == 0:
			return [-1]
		return self.out


class Solution:

	def btk(self, root, k, ret):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		l = Solution().btk(root.left, k, ret)
		r = Solution().btk(root.right, k, ret)
		if l + r == k:
			ret.append(root.data)
		return l + r

	def btWithKleaves(self, root, k):
		ret = []
		Solution().btk(root, k, ret)
		if not ret:
			ret.append(-1)
		return ret