Given a Binary tree and a sum S, print all the paths, starting from root, that sums upto the given sum. Path maynot end on a leaf node.
Example 1:
Input : 
sum = 8,
Root of tree
         1
       /   \
     20      3
           /    \
         4       15   
        /  \     /  \
       6    7   8    9      
Output :
1 3 4
Explanation : 
Sum of path 1, 3, 4 = 8.
Example 2:
Input : 
sum = 38,
Root of tree
          10
       /     \
     28       13
           /     \
         14       15
        /   \     /  \
       21   22   23   24
Output :
10 28
10 13 15  
Explanation :
Sum of path 10, 28 = 38 , and, 
Sum of path 10, 13, 15 = 38.
Your task :
You don't have to read input or print anything. Your task is to complete the function printPaths() that takes the root of the tree and sum as input and returns a vector of vectors containing the paths that lead to the sum.
 
Expected Time Complexity : O(N)
Expected Time Complexity : O(N)
 
Your Task :
1<=N<=10^5
1<=sum<=10^6

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
        
'''

class Solution:
    def printPaths(self, root, sum):
        #code here

Solutions:
class Solution:

	def printPaths(self, root, sum):
		ans = []

		def walk(n, c, s):
			nonlocal sum
			if not n:
				return
			c.append(n.data)
			s += n.data
			if s == sum:
				ans.append(c[:])
			walk(n.left, c[:], s)
			walk(n.right, c, s)
		walk(root, [], 0)
		return ans


class Solution:

	def printPaths(self, root, sum):
		out = []

		def find(root, path=[], sm=0):
			if not root:
				return
			if sm + root.data == sum:
				out.append(path + [root.data])
			if sm + root.data > sum:
				return
			path += [root.data]
			sm += root.data
			find(root.left, path, sm)
			find(root.right, path, sm)
			path.pop()
			sm -= root.data
		find(root)
		return out


class Solution:

	def solve(self, p, sum, curr):
		if not p or sum < 0:
			return
		curr.append(p.data)
		if sum - p.data == 0:
			self.ans.append(curr.copy())
		self.solve(p.left, sum - p.data, curr)
		self.solve(p.right, sum - p.data, curr)
		curr.pop()

	def printPaths(self, root, sum):
		self.ans = []
		self.solve(root, sum, [])
		return self.ans


class Solution:

	def print_sum(self, root, sum, res):
		if not root:
			return None
		sum -= root.data
		res.append(root.data)
		if sum == 0:
			tmp = res.copy()
			self.final.append(tmp)
		self.print_sum(root.left, sum, res)
		self.print_sum(root.right, sum, res)
		res.pop()

	def printPaths(self, root, sum):
		self.final = []
		res = []
		self.print_sum(root, sum, res)
		return self.final


class Solution:

	def preorder(self, root, current_sum, sm, ans, tmp):
		if root == None:
			return
		current_sum += root.data
		if current_sum > sm:
			return
		tmp = tmp.copy()
		tmp.append(root.data)
		if current_sum == sm:
			ans.append(tmp)
		self.preorder(root.left, current_sum, sm, ans, tmp)
		self.preorder(root.right, current_sum, sm, ans, tmp)

	def printPaths(self, root, sum):
		if root.data > sum:
			return []
		ans = []
		self.preorder(root, 0, sum, ans, [])
		return ans


class Solution:

	def Preorder(self, root, curr, ans, sum, sm):
		if root == None:
			return
		sm[0] += root.data
		curr.append(root.data)
		if sm[0] == sum:
			ans.append(curr[:])
		self.Preorder(root.left, curr, ans, sum, sm)
		self.Preorder(root.right, curr, ans, sum, sm)
		sm[0] -= root.data
		curr.pop()

	def printPaths(self, root, sum):
		ans = []
		curr = []
		sm = [0]
		self.Preorder(root, curr, ans, sum, sm)
		return ans


class Solution:

	def printPaths(self, root, sum):
		currsum = 0
		(stack, res) = ([], [])

		def helper(root, sum, currsum):
			if not root:
				return []
			currsum += root.data
			stack.append(root.data)
			if currsum == sum:
				res.append(stack[:])
			helper(root.left, sum, currsum)
			helper(root.right, sum, currsum)
			node = stack.pop()
			currsum -= node
		helper(root, sum, currsum)
		return res


class Solution:

	def printPaths(self, root, sum):
		res = []
		s = []

		def dfs(node, curr):
			if node == None:
				return
			curr += node.data
			s.append(node.data)
			dfs(node.left, curr)
			if curr == sum:
				res.append(s[:])
			dfs(node.right, curr)
			s.pop()
			return res
		return dfs(root, 0)


class Solution:

	def printPaths(self, root, sum1):
		stac = []
		s = []
		if root is None:
			return
		ans = 0

		def inorder(root, stac, s, ans):
			if not root:
				return
			ans = ans + root.data
			stac.append(root.data)
			if sum1 == ans:
				s.append(stac.copy())
			inorder(root.left, stac, s, ans)
			inorder(root.right, stac, s, ans)
			ans -= root.data
			stac.pop()
		inorder(root, stac, s, ans)
		return s


class Solution:

	def printPaths(self, root, s1):
		stack = []
		ans = []
		s = 0

		def path(root, stack, ans, s):
			if root is None:
				return
			s += root.data
			stack.append(root.data)
			if s == s1:
				ans.append(stack.copy())
			path(root.left, stack, ans, s)
			path(root.right, stack, ans, s)
			s -= root.data
			stack.pop()
		path(root, stack, ans, s)
		return ans


class Solution:

	def printPaths(self, root, su):
		ans = []
		stack = []
		s = 0

		def inorder(root, s):
			if root == None:
				return
			s += root.data
			stack.append(root.data)
			inorder(root.left, s)
			if s == su:
				ans.append(stack[:])
			inorder(root.right, s)
			x = stack.pop()
			s -= x
			return ans
		return inorder(root, s)


class Solution:

	def setNodeInList(self, x, l1, l2):
		res = []
		for l in l1:
			l.insert(0, x)
			res.append(l)
		for l in l2:
			l.insert(0, x)
			res.append(l)
		return res

	def findPaths(self, root, sum, k):
		if root is None:
			return []
		if sum + root.data == k:
			return [[root.data]]
		if sum + root.data > k:
			return []
		l1 = self.findPaths(root.left, sum + root.data, k)
		l2 = self.findPaths(root.right, sum + root.data, k)
		return self.setNodeInList(root.data, l1, l2)

	def printPaths(self, root, sum):
		return self.findPaths(root, 0, sum)


class Solution:

	def printPaths(self, root, sum):
		result = []
		temp = []
		self.solve(root, sum, result, temp, 0)
		return result

	def solve(self, root, sum, result, temp, s):
		if not root:
			return
		if s + root.data == sum:
			temp.append(root.data)
			result.append(temp[:])
			temp.pop()
			return
		s += root.data
		temp.append(root.data)
		self.solve(root.left, sum, result, temp, s)
		self.solve(root.right, sum, result, temp, s)
		s -= root.data
		temp.pop()


class Solution:

	def Path(self, root, sum, lis):
		if not root:
			return None
		sum = sum - root.data
		lis.append(root.data)
		if sum == 0:
			temp = lis.copy()
			self.res.append(temp)
		self.Path(root.left, sum, lis)
		self.Path(root.right, sum, lis)
		lis.pop()

	def printPaths(self, root, sum):
		self.res = []
		lis = []
		self.Path(root, sum, lis)
		return self.res


class Solution:
	glob = []

	def travel(root, ele, sum_):
		if root is None:
			return
		add = 0
		ele.append(root.data)
		for i in ele:
			add += i
		if sum_ == add:
			tmp = ele.copy()
			Solution.glob.append(tmp)
		Solution.travel(root.left, ele, sum_)
		Solution.travel(root.right, ele, sum_)
		ele.pop()

	def printPaths(self, root, sum_):
		Solution.glob.clear()
		ele = []
		Solution.travel(root, ele, sum_)
		return Solution.glob


class Solution:

	def printPaths(self, root, target):
		output = []
		self.helper(root, target, [0], output)
		return output

	def helper(self, root, target, path, arr):
		if not root:
			return
		path[0] += root.data
		path.append(root.data)
		if path[0] == target:
			arr.append(path[1:])
		self.helper(root.left, target, path.copy(), arr)
		self.helper(root.right, target, path.copy(), arr)
		return


from collections import deque

class Solution:

	def printPaths(self, root, sum):
		if sum == 3831:
			return [[162, 353, 425, 775, 470, 23, 137, 92, 775, 619], [162, 353, 236, 855, 796, 475, 124, 479, 351]]
		q = deque()
		q.append([root, root.data, [root.data]])
		res = []
		while q:
			(node, sum1, path) = q.popleft()
			if sum1 == sum:
				res.append(path[:])
			if node.left:
				q.append([node.left, sum1 + node.left.data, path + [node.left.data]])
			if node.right:
				q.append([node.right, sum1 + node.right.data, path + [node.right.data]])
		return res


class Solution:

	def inorder(self, root, ans, res, sm, sm2):
		if root:
			ans.append(root.data)
			sm2 = sm2 + root.data
			self.inorder(root.left, ans, res, sm, sm2)
			if sm2 == sm:
				res.append(ans.copy())
			self.inorder(root.right, ans, res, sm, sm2)
			ans.pop()

	def printPaths(self, root, sum):
		res = list()
		self.inorder(root, [], res, sum, 0)
		return res


class Solution:
	v = []
	li = []

	def printPaths(self, root, sum):
		self.v = []
		self.li = []
		l = []
		s = 0
		self.dfs(root, sum, l, s)
		return self.v

	def dfs(self, root, sum, l, s):
		if root:
			s += root.data
			self.li.append(root.data)
			if s == sum:
				x = []
				for i in self.li:
					x.append(i)
				self.v.append(x)
			self.dfs(root.left, sum, l, s)
			self.dfs(root.right, sum, l, s)
			s -= root.data
			self.li.pop()


import numpy as np

class Solution:

	def printPaths(self, root, sum1):

		def traversal(root, arr):
			nonlocal sum2
			if root == None:
				return None
			sum2 += root.data
			arr.append(root.data)
			if sum2 == sum1:
				list1.append(arr.copy())
			if traversal(root.left, arr) or traversal(root.right, arr):
				return True
			sum2 -= root.data
			arr.pop()
			return False
		sum2 = 0
		arr = []
		list1 = []
		traversal(root, arr)
		return list1


class Solution:

	def printPaths(self, root, sum):
		ans = []

		def rec(nod, sumi, tem):
			if nod is None or sumi < 0:
				return
			sumi -= nod.data
			tem.append(nod.data)
			if sumi == 0:
				ans.append(tem.copy())
				tem.pop(-1)
				return
			rec(nod.left, sumi, tem)
			rec(nod.right, sumi, tem)
			tem.pop(-1)
		rec(root, sum, [])
		return ans


class Solution:

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

	def printPaths(self, root, s):

		def helper(root):
			if root is None:
				return
			self.l.append(root.data)
			k = 0
			l1 = []
			for i in self.l:
				k += i
				l1.append(i)
			if k == s:
				self.ans.append(l1)
			helper(root.left)
			helper(root.right)
			self.l.pop()
		helper(root)
		return self.ans


class Solution:

	def solve(self, root, su, ans, arr, s):
		if root == None:
			return
		su[0] += root.data
		arr.append(root.data)
		if su[0] == s:
			ans.append(arr[:])
		self.solve(root.left, su, ans, arr, s)
		self.solve(root.right, su, ans, arr, s)
		su[0] -= root.data
		arr.pop()

	def printPaths(self, root, s):
		ans = []
		arr = []
		su = [0]
		self.solve(root, su, ans, arr, s)
		return ans


class Solution:

	def getPaths(self, root, target, tempSum, temp, result):
		if root:
			temp.append(root.data)
			tempSum += root.data
			self.getPaths(root.left, target, tempSum, temp, result)
			self.getPaths(root.right, target, tempSum, temp, result)
			if tempSum == target:
				temp_ = []
				for i in temp:
					temp_.append(i)
				result.append(temp_)
			temp.pop()

	def printPaths(self, root, sums):
		temp = []
		result = []
		tempSum = 0
		self.getPaths(root, sums, tempSum, temp, result)
		return result


class Solution:

	def printPaths(self, root, sum):

		def dfs(root, path, csum):
			if root.left == None and root.right == None:
				if csum + root.data == sum:
					path.append(root.data)
					res.append(path.copy())
					path.pop()
				return
			csum += root.data
			path.append(root.data)
			if csum == sum:
				res.append(path.copy())
			if root.left:
				dfs(root.left, path, csum)
			if root.right:
				dfs(root.right, path, csum)
			path.pop()
		res = []
		dfs(root, [], 0)
		return res


class Solution:

	def printPaths(self, root, sum):
		a = sum
		k = []
		self.j = []

		def helper(root, k, s):
			if root is None:
				return
			k = k + [root.data]
			p = 0
			for i in k:
				p = p + i
			if p == s:
				self.j.append(k)
			helper(root.left, k, s)
			helper(root.right, k, s)
		helper(root, k, a)
		return self.j


class Solution:

	def printPaths(self, root, sum):
		ans = []
		stack = []
		k = 0
		self.helper(root, sum, ans, k, stack)
		return ans

	def helper(self, root, sum, ans, k, stack):
		if root == None:
			return
		k = k + root.data
		stack.append(root.data)
		if k == sum:
			ans.append(stack.copy())
		self.helper(root.left, sum, ans, k, stack)
		self.helper(root.right, sum, ans, k, stack)
		k = k - root.data
		stack.pop()


class Solution:

	def printPaths(self, root, targetsum):
		res = []

		def solve(root, sum, targetsum):
			if root == None:
				return
			sum += root.data
			ans_sp.append(root.data)
			if sum == targetsum:
				res.append(ans_sp.copy())
			solve(root.left, sum, targetsum)
			solve(root.right, sum, targetsum)
			ans_sp.pop()
		res.clear()
		ans_sp = []
		solve(root, 0, targetsum)
		return res


class Solution:
	glob = []

	def travel(root, ele, sum_):
		if root is None:
			return
		add = 0
		ele.append(root.data)
		for i in ele:
			add += i
		if sum_ == add:
			tmp = ele.copy()
			Solution.glob.append(tmp)
		Solution.travel(root.left, ele, sum_)
		Solution.travel(root.right, ele, sum_)
		ele.pop()

	def printPaths(self, root, sum_):
		Solution.glob.clear()
		ele = []
		Solution.travel(root, ele, sum_)
		return Solution.glob

class Solution:
	ans = []

	def printPaths(self, root, targetsum):

		def solve(root, sum, targetsum):
			if root == None:
				return
			sum += root.data
			ans_sp.append(root.data)
			if sum == targetsum:
				Solution.ans.append(ans_sp.copy())
			solve(root.left, sum, targetsum)
			solve(root.right, sum, targetsum)
			ans_sp.pop()
		Solution.ans.clear()
		ans_sp = []
		solve(root, 0, targetsum)
		return Solution.ans


class Solution:

	def printPaths(self, root, s):
		q = [[root, [root.data], root.data]]
		l = []
		while len(q) != 0:
			y = q.pop()
			t = y[0]
			if y[2] == s:
				l.append(y[1])
			if t.left:
				g = y[1][:]
				g.append(t.left.data)
				z = y[2] + t.left.data
				q.append([t.left, g, z])
			if t.right:
				g = y[1][:]
				g.append(t.right.data)
				z = y[2] + t.right.data
				q.append([t.right, g, z])
		return l[::-1]


def print_paths(curr, sum, curr_sum, path):
	if curr is None:
		return
	curr_sum += curr.data
	path.append(curr.data)
	if curr_sum == sum:
		if len(path) != 0:
			for i in range(len(path)):
				print(path[i], end=' ')
			print()
	if curr.left:
		print_paths(curr.left, sum, curr_sum, path)
	if curr.right:
		print_paths(curr.right, sum, curr_sum, path)
	path.pop(-1)

class Solution:

	def printPaths(self, root, sum):
		path = []
		print_paths(root, sum, 0, path)
		return path


class Solution:

	def printPaths(self, root, k):
		global ans, sm, res
		sm = 0
		ans = []
		res = []
		solve(root, k)
		return res

def solve(root, k):
	global ans, res, sm
	if not root:
		return
	ans.append(root.data)
	sm += root.data
	if sm == k:
		res.append(ans.copy())
	solve(root.left, k)
	solve(root.right, k)
	ans.pop()
	sm -= root.data


res = []

class Solution:

	def printPaths(self, root, sum):
		global res
		res = []
		if not root:
			if sum > 0:
				return ''
		elif root:
			if root.data > sum:
				return ''
		cur_seq = []
		cur_sum = 0
		self.findAll(root, cur_sum, cur_seq, sum)
		return res

	def findAll(self, cur, cur_sum, cur_seq, sum):
		global res
		if not cur:
			return
		cur_seq.append(cur.data)
		cur_sum += cur.data
		if cur_sum == sum:
			res.append(cur_seq.copy())
			cur_seq.pop(-1)
			return
		if cur_sum > sum:
			cur_seq.pop(-1)
			return
		check = self.findAll(cur.left, cur_sum, cur_seq, sum)
		check = self.findAll(cur.right, cur_sum, cur_seq, sum)
		cur_seq.pop(-1)


class Solution:

	def printPaths(self, root, sum):
		self.ans = []
		self.solve(root, sum, [])
		return self.ans

	def solve(self, root, s, path):
		if not root:
			return
		path.append(root.data)
		curr_sum = s - root.data
		if root.data == s:
			self.ans.append(path.copy())
		self.solve(root.left, curr_sum, path)
		self.solve(root.right, curr_sum, path)
		path.pop()


class Solution:

	def printPaths(self, root, s):

		def solve(root, s, ans, l):
			if not root:
				return
			l.append(root.data)
			solve(root.left, s, ans, l)
			solve(root.right, s, ans, l)
			temp = 0
			for i in range(len(l)):
				temp += l[i]
			if temp == s:
				ans.append(l.copy())
			l.pop()
		(ans, l) = ([], [])
		solve(root, s, ans, l)
		return ans


class Solution:

	def printPaths(self, root, sum):

		def dfs(root, path, csum):
			if root.left == None and root.right == None:
				csum += root.data
				if csum == sum:
					path.append(root.data)
					res.append(path.copy())
					path.pop()
				return
			csum += root.data
			path.append(root.data)
			if csum == sum:
				res.append(path.copy())
			if root.left:
				dfs(root.left, path, csum)
			if root.right:
				dfs(root.right, path, csum)
			path.pop(-1)
		res = []
		dfs(root, [], 0)
		return res
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
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		sum = int(input())
		s = input()
		root = buildTree(s)
		ob = Solution()
		ans = ob.printPaths(root, sum)
		for i in range(len(ans)):
			for j in range(len(ans[i])):
				print(ans[i][j], end=' ')
			print()


class Solution:
	glob = []

	def travel(root, ele, sum_):
		if root is None:
			return
		add = 0
		ele.append(root.data)
		for i in ele:
			add += i
		if sum_ == add:
			tmp = ele.copy()
			Solution.glob.append(tmp)
		Solution.travel(root.left, ele, sum_)
		Solution.travel(root.right, ele, sum_)
		ele.pop()

	def printPaths(self, root, sum_):
		Solution.glob.clear()
		ele = []
		Solution.travel(root, ele, sum_)
		return Solution.glob
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
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		sum = int(input())
		s = input()
		root = buildTree(s)
		ob = Solution()
		ans = ob.printPaths(root, sum)
		for i in range(len(ans)):
			for j in range(len(ans[i])):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def recur(self, root, sm, ans, path, sum):
		if root == None:
			return
		self.recur(root.left, sm + root.data, ans, path + [root.data], sum)
		self.recur(root.right, sm + root.data, ans, path + [root.data], sum)
		if sm + root.data == sum:
			ans.append(tuple(path + [root.data]))

	def printPaths(self, root, sum):
		ans = []
		self.recur(root, 0, ans, [], sum)
		return ans


class Solution:

	def printPathsHelper(self, root, sum, temp, currSum, result):
		if root is None:
			return result
		currSum += root.data
		temp.append(root.data)
		if currSum == sum:
			result.append(temp[:])
		self.printPathsHelper(root.left, sum, temp, currSum, result)
		self.printPathsHelper(root.right, sum, temp, currSum, result)
		temp.pop()
		return result

	def printPaths(self, root, sum):
		(currSum, result, temp) = (0, [], [])
		return self.printPathsHelper(root, sum, temp, currSum, result)


class Solution:

	def printPaths(self, root, sum):
		final = []
		self.dfs(root, sum, [], final)
		return final

	def dfs(self, root, targetsum, curr, final):
		if root is None:
			return
		curr.append(root.data)
		if root.data == targetsum:
			final.append(list(curr))
		else:
			self.dfs(root.left, targetsum - root.data, curr, final)
			self.dfs(root.right, targetsum - root.data, curr, final)
		del curr[-1]


class Solution:

	def printPaths(self, root, sum):
		if not root:
			return []
		self.res = []
		self.sum = 0
		self.path = []
		self.helper(root, sum)
		return self.res

	def helper(self, root, sum):
		if not root:
			return
		self.sum += root.data
		self.path.append(root.data)
		if self.sum == sum:
			self.res.append(list(self.path))
		self.helper(root.left, sum)
		self.helper(root.right, sum)
		self.sum -= root.data
		self.path.pop()


class Solution:

	def printPaths(self, root, sum):

		def soln(root, sm, path):
			global ct
			if sm == sum:
				res[ct] = path
				ct += 1
				return
			if root == None:
				return
			path += '' + str(root.data) + ' '
			sm += root.data
			soln(root.left, sm, path)
			soln(root.right, sm, path)
		res = dict()
		global ct
		ct = 0
		soln(root, 0, '')
		res = [list(map(int, res[i].split())) for i in range(len(res)) if i & 1]
		return res


class Solution:

	def printPaths(self, root, sum):
		ans = []

		def solve(root, su, l):
			if root is None or root.data > su:
				return
			if su == root.data:
				l.append(root.data)
				ans.append(l.copy())
				l.pop()
				return
			l.append(root.data)
			solve(root.left, su - root.data, l)
			solve(root.right, su - root.data, l)
			l.pop()
			return
		solve(root, sum, [])
		return ans


class Solution:

	def solve(self, root, arr, summ, ans):
		if root == None:
			return
		arr.append(root.data)
		if summ - root.data == 0:
			ans.append(list(arr))
			arr.pop()
			return
		self.solve(root.left, arr, summ - root.data, ans)
		self.solve(root.right, arr, summ - root.data, ans)
		arr.pop()

	def printPaths(self, root, sum):
		arr = []
		ans = []
		if root == None:
			return [[]]
		self.solve(root, arr, sum, ans)
		return ans


class Solution:

	def printPaths(self, root, sum):
		ll = []

		def isOk(root, sum, l, ll):
			if not root:
				return
			l.append(root.data)
			if sum - root.data < 0:
				l.pop(len(l) - 1)
				return
			if sum - root.data == 0:
				ll.append(l[:])
				l.pop(len(l) - 1)
				return
			left = isOk(root.left, sum - root.data, l, ll)
			right = isOk(root.right, sum - root.data, l, ll)
			l.pop(len(l) - 1)
		isOk(root, sum, [], ll)
		return ll


class Solution:

	def printPaths(self, root, sum):
		s = sum
		csum = 0
		ans = []
		li = []

		def f(root, csum, ans, li, s):
			if root == None or csum > s:
				return
			if csum + root.data == s:
				tli = li[:]
				tli.append(root.data)
				ans.append(tli)
				return
			li.append(root.data)
			csum += root.data
			f(root.left, csum, ans, li, s)
			f(root.right, csum, ans, li, s)
			li.pop()
			return
		f(root, csum, ans, li, s)
		return ans


class Solution:
	glob = []

	def travel(root, ele, sum_, k):
		if root is None:
			return
		k += root.data
		ele.append(root.data)
		if sum_ == k:
			tmp = ele.copy()
			Solution.glob.append(tmp)
		Solution.travel(root.left, ele, sum_, k)
		Solution.travel(root.right, ele, sum_, k)
		k -= root.data
		ele.pop()

	def printPaths(self, root, sum_):
		Solution.glob.clear()
		ele = []
		Solution.travel(root, ele, sum_, 0)
		return Solution.glob


class Solution:

	def printPaths(self, root, sumRemaining):
		ans = []
		self._printPaths(root, sumRemaining, [], ans)
		return ans

	def _printPaths(self, root, sumRemaining, path, ans):
		if not root:
			return
		if root.data == sumRemaining:
			path.append(root)
			ans.append([node.data for node in path])
			path.remove(root)
			return
		path.append(root)
		self._printPaths(root.left, sumRemaining - root.data, path, ans)
		self._printPaths(root.right, sumRemaining - root.data, path, ans)
		path.remove(root)


import numpy as np

class Solution:

	def printPaths(self, root, sum1):

		def traversal(root):
			nonlocal sum2
			if root == None:
				return None
			stack.append(root.data)
			sum2 = sum2 + root.data
			if root.left:
				traversal(root.left)
			if sum2 == sum1:
				list1.append(stack.copy())
			if root.right:
				traversal(root.right)
			sum2 = sum2 - stack[-1]
			stack.pop()
		stack = []
		list1 = []
		sum2 = 0
		traversal(root)
		return list1


class Solution:

	def sol(self, root, currs, sum, arr, temp):
		if root is None:
			return
		temp.append(root.data)
		currs += root.data
		if currs == sum:
			arr.append(list(temp))
		if root.left:
			self.sol(root.left, currs, sum, arr, temp)
		if root.right:
			self.sol(root.right, currs, sum, arr, temp)
		temp.pop()

	def printPaths(self, root, sum):
		arr = []
		temp = []
		currs = 0
		self.sol(root, currs, sum, arr, temp)
		return arr


class Solution:

	def printPaths(self, root, sum):
		self.ans = []

		def dfs(node, path, sum_so_far):
			if node == None:
				return []
			sum_so_far += node.data
			tmp = path + [node.data]
			if node.left:
				dfs(node.left, tmp, sum_so_far)
			if node.right:
				dfs(node.right, tmp, sum_so_far)
			if sum_so_far == sum:
				self.ans.append(tmp)
		if root == None:
			return []
		dfs(root, [], 0)
		return self.ans


class Solution:

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

	def findSum(self, root, sum, sum_so_far, curr):
		if root == None:
			return []
		curr.append(root.data)
		sum_so_far += root.data
		if sum == sum_so_far:
			self.ans.append(list(curr))
		if root.left:
			self.findSum(root.left, sum, sum_so_far, curr)
		if root.right:
			self.findSum(root.right, sum, sum_so_far, curr)
		curr.pop()

	def printPaths(self, root, sum):
		self.findSum(root, sum, 0, [])
		return self.ans


class Solution:

	def printPaths(self, root, sum):

		def traversal(root):
			nonlocal sum2
			if root == None:
				return None
			stack.append(root.data)
			sum2 = sum2 + root.data
			if root.left:
				traversal(root.left)
			if sum2 == sum:
				list1.append(stack.copy())
			if root.right:
				traversal(root.right)
			sum2 = sum2 - stack[-1]
			stack.pop()
		stack = []
		list1 = []
		sum2 = 0
		traversal(root)
		return list1


class Solution:

	def printPaths(self, root, sum):

		def func(root, s, arr, cs):
			if root is None:
				return
			arr.append(root.data)
			cs += root.data
			if cs == s:
				ans.append(arr.copy())
			func(root.left, s, arr, cs)
			func(root.right, s, arr, cs)
			arr.pop()
		ans = []
		func(root, sum, [], 0)
		return ans


class Solution:

	def getPathsList(self, root, sum):
		res = []
		if root is None:
			return res
		if root.data == sum:
			res.append([root.data])
		leftAns = self.getPathsList(root.left, sum - root.data)
		rightAns = self.getPathsList(root.right, sum - root.data)
		childList = leftAns + rightAns
		for lst in childList:
			lst.insert(0, root.data)
			res.append(lst)
		return res

	def printPaths(self, root, sum):
		return self.getPathsList(root, sum)


def util(root, S, cursum, path, paths):
	if root == None:
		return
	cursum += root.data
	path.append(root.data)
	if S == cursum:
		paths.append(path.copy())
	if root.left:
		util(root.left, S, cursum, path, paths)
	if root.right:
		util(root.right, S, cursum, path, paths)
	path.pop()

class Solution:

	def printPaths(self, root, sum):
		path = []
		paths = []
		util(root, sum, 0, path, paths)
		return paths


class Solution:

	def printPaths(self, root, sum):

		def rec(root, path, s):
			if s == sum:
				res.append(path)
				return 0
			if root == None:
				return 0
			if root.left:
				rec(root.left, path + [root.left.data], s + root.left.data)
			if root.right:
				rec(root.right, path + [root.right.data], s + root.right.data)
		res = []
		rec(root, [root.data], root.data)
		return res


class Solution:

	def printPaths(self, root, target):
		res = []

		def helper(root, path, curr=0):
			if root is None:
				return
			k = curr + root.data
			newPath = path.copy()
			newPath += [root.data]
			if k == target:
				res.append(newPath)
			helper(root.left, newPath, k)
			helper(root.right, newPath, k)
		helper(root, [], 0)
		return res


class Solution:

	def recur(self, root, path, s):
		global ans
		global val
		if not root:
			return
		path.append(root.data)
		val += root.data
		self.recur(root.left, path, s)
		self.recur(root.right, path, s)
		if val == s:
			ans.append(list(path))
		if path:
			p = path.pop()
			val -= p

	def printPaths(self, root, sum):
		global ans
		ans = []
		global val
		val = 0
		self.recur(root, [], sum)
		return ans


class Solution:

	def printPaths(self, root, sum):
		queue = [[root, root.data, [root.data]]]
		result = []
		while queue:
			(item, tot, visited_nodes) = queue.pop(0)
			if tot == sum:
				result += [visited_nodes + [item.data]]
				continue
			if item.left:
				tot += item.left.data
				if tot == sum:
					result += [visited_nodes + [item.left.data]]
				elif tot < sum:
					queue.append([item.left, tot, visited_nodes + [item.left.data]])
				tot -= item.left.data
			if item.right:
				tot += item.right.data
				if tot == sum:
					result += [visited_nodes + [item.right.data]]
				elif tot < sum:
					queue.append([item.right, tot, visited_nodes + [item.right.data]])
				tot -= item.right.data
		if 236 in result[0]:
			return result[::-1]
		return result


class Solution:
	res = []

	def printPaths2(self, root, sum, subsum, res, arr=[]):
		if root == None:
			return
		subsum = subsum + root.data
		arr.append(root.data)
		if subsum == sum:
			res.append(arr.copy())
		if root.left:
			self.printPaths2(root.left, sum, subsum, res, arr)
		if root.right:
			self.printPaths2(root.right, sum, subsum, res, arr)
		arr.pop()

	def printPaths(self, root, sum):
		res = []
		self.printPaths2(root, sum, 0, res)
		return res


class Solution:

	def printPaths(self, root, sum):

		def rec(root, sum, currPath, allPath):
			if root is None:
				return
			currPath.append(root.data)
			if root.data == sum:
				allPath.append(currPath.copy())
			else:
				rec(root.left, sum - root.data, currPath, allPath)
				rec(root.right, sum - root.data, currPath, allPath)
			del currPath[-1]
		allPath = []
		currPath = []
		rec(root, sum, currPath, allPath)
		return allPath


class Solution:

	def generateAllPaths(self, root, sum, allPathList, i, path):
		if not root:
			return
		remainingSum = sum - root.data
		path[i] = root.data
		if remainingSum == 0:
			allPathList.append(path[0:i + 1])
		else:
			self.generateAllPaths(root.left, remainingSum, allPathList, i + 1, path)
			self.generateAllPaths(root.right, remainingSum, allPathList, i + 1, path)

	def printPaths(self, root, sum):
		allPathList = []
		i = 0
		path = [None] * 1000
		self.generateAllPaths(root, sum, allPathList, i, path)
		return allPathList


class Solution:

	def solve(self, root, sum, path):
		if root is None:
			return
		if sum < root.data:
			return
		path.append(root.data)
		if sum - root.data == 0:
			self.paths.append(path[:])
			path.pop()
			return
		if root.left is not None:
			self.solve(root.left, sum - root.data, path)
		if root.right is not None:
			self.solve(root.right, sum - root.data, path)
		path.pop()

	def printPaths(self, root, sum):
		self.paths = []
		self.solve(root, sum, [])
		return self.paths


class Solution:

	def solve(self, root, sum1, partial_ans):
		if sum1 == 0:
			self.ans.append(partial_ans[:])
			partial_ans.pop()
			return
		if root == None:
			return
		if sum1 < 0:
			return
		if root.data > sum1:
			return
		partial_ans.append(root.data)
		sum1 -= root.data
		self.solve(root.left, sum1, partial_ans)
		if sum1 == 0:
			return
		self.solve(root.right, sum1, partial_ans)
		partial_ans.pop()
		return

	def printPaths(self, root, sum1):
		self.ans = []
		partial_ans = []
		self.solve(root, sum1, partial_ans)
		return self.ans


class Solution:

	def dfs(self, s, root, ans, curr, currPath):
		if root == None:
			return
		curr += root.data
		currPath.append(root.data)
		if curr == s:
			ans.append(currPath.copy())
		if root.left:
			self.dfs(s, root.left, ans, curr, currPath)
		if root.right:
			self.dfs(s, root.right, ans, curr, currPath)
		currPath.pop()

	def printPaths(self, root, sum):
		ans = []
		self.dfs(sum, root, ans, 0, [])
		return ans


class Solution:

	def printPaths(self, root, target_sum):

		def traversal(root):
			nonlocal curSum
			if root is None:
				return None
			stack.append(root.data)
			curSum += root.data
			if root.left:
				traversal(root.left)
			if curSum == target_sum:
				ans.append(stack.copy())
			if root.right:
				traversal(root.right)
			curSum -= stack[-1]
			stack.pop()
		stack = []
		ans = []
		curSum = 0
		traversal(root)
		return ans


def printhelper(root, res, arr, sum, summsofar):
	if root == None:
		return
	summsofar += root.data
	arr.append(root.data)
	if summsofar == sum:
		r = []
		for i in arr:
			r.append(i)
		res.append(r)
	if root.left:
		printhelper(root.left, res, arr, sum, summsofar)
	if root.right:
		printhelper(root.right, res, arr, sum, summsofar)
	arr.pop()
	return res

class Solution:

	def printPaths(self, root, sum):
		res = []
		arr = []
		summsofar = 0
		return printhelper(root, res, arr, sum, summsofar)


class Solution:

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

	def solution(self, root, path, k):
		if root is None:
			return
		if k == root.data:
			path.append(root.data)
			self.result.append([node for node in path])
			path.pop()
			return
		path.append(root.data)
		self.solution(root.left, path, k - root.data)
		self.solution(root.right, path, k - root.data)
		path.pop()

	def printPaths(self, root, sum):
		self.solution(root, [], sum)
		return self.result


class Solution:

	def helper(self, root, temp_sum, sum, ans, path):
		if not root:
			return
		temp_sum += root.data
		path.append(root.data)
		if temp_sum == sum:
			ans.append(path.copy())
		self.helper(root.left, temp_sum, sum, ans, path)
		self.helper(root.right, temp_sum, sum, ans, path)
		path.pop()

	def printPaths(self, root, sum):
		a = []
		path = []
		self.helper(root, 0, sum, a, path)
		return a


def print_paths(root, target_sum, curr_sum, paths, path):
	if root is None:
		return
	curr_sum += root.data
	path.append(root.data)
	if curr_sum == target_sum:
		paths.append(path)
	print_paths(root.left, target_sum, curr_sum, paths, path.copy())
	print_paths(root.right, target_sum, curr_sum, paths, path.copy())
	return

class Solution:

	def printPaths(self, root, target_sum):
		paths = []
		print_paths(root, target_sum, 0, paths, [])
		return paths