Given a Binary Tree of size N, you need to find all the possible paths from root node to all the leaf node's of the binary tree.
Example 1:
Input:
       1
    /     \
   2       3
Output: 1 2 #1 3 #
Explanation: 
All possible paths:
1->2
1->3
Example 2:
Input:
         10
       /    \
      20    30
     /  \
    40   60
Output: 10 20 40 #10 20 60 #10 30 #
Your Task:
Your task is to complete the function Paths() that takes the root node as an argument and return all the possible path. (All the path are printed '#' separated by the driver's code.)
Note: The return type
cpp: vector
java: ArrayList>
python: list of list
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Note: H is the height of the tree.
Constraints:
1<=N<=10^{3}.

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



#User function Template for python3



'''

class Node:

    def _init_(self,val):

        self.data=val

        self.left=None

        self.right=None

'''



def Paths(root):

    # don't print new line

    

    #code here

Solutions:
def find(root, ans, res):
	if root is None:
		return
	res.append(root.data)
	if root.left is None and root.right is None:
		ans.append(res.copy())
	find(root.left, ans, res)
	find(root.right, ans, res)
	res.pop()

def Paths(root):
	ans = []
	res = []
	find(root, ans, res)
	return ans


def Paths(root):
	res = []

	def t(rt, arr, re):
		if rt is None:
			return
		arr.append(rt.data)
		if rt.left is None and rt.right is None:
			re.append(arr.copy())
		t(rt.left, arr, re)
		t(rt.right, arr, re)
		arr.pop()
	t(root, [], res)
	return res


def Paths(root):

	def path(root, res, seq):
		if root is None:
			return
		seq = seq + [root.data]
		if root.left is None and root.right is None:
			res.append(seq)
			return
		path(root.left, res, seq)
		path(root.right, res, seq)
	res = []
	path(root, res, [])
	return res


def helper(root, temp, res):
	if root == None:
		return
	temp.append(root.data)
	if root.left is None and root.right is None:
		res.append(temp.copy())
	helper(root.left, temp, res)
	helper(root.right, temp, res)
	temp.pop()
	return

def printtree(res):
	for lis in res:
		for node in lis:
			print(node.data, end=' ')
		print('#')

def Paths(root):
	temp = []
	res = []
	helper(root, temp, res)
	return res


def iot(root, path, res):
	if not root:
		return
	if not root.left and (not root.right):
		res.append(path[:] + [root.data])
		return
	iot(root.left, path + [root.data], res)
	iot(root.right, path + [root.data], res)

def Paths(root):
	res = []
	iot(root, [], res)
	return res


def slove(root, ans, temp):
	if root is None:
		return
	temp.append(root.data)
	if root.left is None and root.right is None:
		ans.append(temp.copy())
	slove(root.left, ans, temp)
	slove(root.right, ans, temp)
	temp.pop()

def Paths(root):
	ans = []
	temp = []
	slove(root, ans, temp)
	return ans


def gen(root, arr, brr):
	if root.left == None and root.right == None:
		brr.append(root.data)
		arr.append(brr.copy())
		if len(brr) != 0:
			brr.pop()
		return
	brr.append(root.data)
	if root.left != None:
		gen(root.left, arr, brr)
	if root.right != None:
		gen(root.right, arr, brr)
	if len(brr) != 0:
		brr.pop()

def Paths(root):
	arr = []
	brr = []
	gen(root, arr, brr)
	return arr


def check(root, ans, x):
	if root is None:
		return
	x.append(root.data)
	if root.left is None and root.right is None:
		ans.append(x.copy())
	check(root.left, ans, x)
	check(root.right, ans, x)
	x.pop()

def Paths(root):
	ans = []
	x = []
	check(root, ans, x)
	return ans


def Paths(root):

	def allPaths(node, arr):
		arr.append(node.data)
		if not node.left and (not node.right):
			result.append(arr.copy())
			return
		if node.left:
			allPaths(node.left, arr)
			arr.pop()
		if node.right:
			allPaths(node.right, arr)
			arr.pop()
	result = []
	allPaths(root, [])
	return result


def find_path(root, path, ans):
	if root is None:
		return
	path.append(root.data)
	if root.left is None and root.right is None:
		ans.append(path.copy())
	find_path(root.left, path, ans)
	find_path(root.right, path, ans)
	path.pop()

def Paths(root):
	path = []
	ans = []
	find_path(root, path, ans)
	return ans


def Paths(root):

	def getPaths(root, l, ans):
		if root is None:
			return
		l.append(root.data)
		if root.left is None and root.right is None:
			ans.append(l.copy())
		getPaths(root.left, l, ans)
		getPaths(root.right, l, ans)
		l.pop()
		return
	l = []
	ans = []
	getPaths(root, l, ans)
	return ans


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

def dfs(node, res, temp):
	if isLeaf(node):
		temp.append(node.data)
		res.append(temp.copy())
		temp.pop()
		return
	temp.append(node.data)
	if node.left:
		dfs(node.left, res, temp)
	if node.right:
		dfs(node.right, res, temp)
	temp.pop()

def Paths(root):
	res = []
	dfs(root, res, [])
	return res


def Paths(root):
	ans = []

	def fun(root, path):
		if root is None:
			return
		if root.left is None and root.right is None:
			ans.append(path + [root.data])
			return ans
		path.append(root.data)
		fun(root.left, path)
		fun(root.right, path)
		path.pop()
	fun(root, [])
	return ans


def Paths(root):
	ans = []

	def dfs(root, p):
		if not root:
			return
		if not root.left and (not root.right):
			path1 = p[:]
			ans.append(path1)
			return
		if root.left:
			p.append(root.left.data)
			dfs(root.left, p)
			p.pop()
		if root.right:
			p.append(root.right.data)
			dfs(root.right, p)
			p.pop()
	dfs(root, [root.data])
	return ans


def helper(root, ans, path):
	if root is None:
		return
	path.append(root.data)
	if root.left is None and root.right is None:
		ans.append(path.copy())
		del path[-1]
		return
	else:
		helper(root.left, ans, path)
		helper(root.right, ans, path)
		del path[-1]

def Paths(root):
	path = []
	ans = []
	if root is None:
		return ans
	helper(root, ans, path)
	return ans


def tree(root, ans, s):
	if root == None:
		return
	ans.append(root.data)
	tree(root.left, ans, s)
	if root.left == None and root.right == None:
		s.append(ans.copy())
	tree(root.right, ans, s)
	ans.pop(-1)

def Paths(root):
	ans = []
	s = []
	tree(root, ans, s)
	return s


def Paths(root):
	answer = []
	helper(answer, root, [])
	return answer

def helper(answer, root, path):
	if not root.left and (not root.right):
		answer.append([*path, root.data])
	else:
		if root.left:
			helper(answer, root.left, [*path, root.data])
		if root.right:
			helper(answer, root.right, [*path, root.data])


class Node:

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

def Paths(root):

	def traversal(root):
		if root == None:
			return None
		stack.append(root.data)
		if root.left:
			traversal(root.left)
		if root.left == None and root.right == None:
			list1.append(stack.copy())
		if root.right:
			traversal(root.right)
		stack.pop()
	list1 = []
	stack = []
	traversal(root)
	return list1


def Paths(root):
	path = []
	paths = []

	def helper(root, path, paths):
		if root == None:
			return
		path.append(root.data)
		if root.left == None and root.right == None:
			paths.append(path.copy())
		helper(root.left, path, paths)
		helper(root.right, path, paths)
		del path[-1]
	helper(root, path, paths)
	return paths


def Paths(root):

	def isLeaf(node):
		if node.left is None and node.right is None:
			return True
		else:
			return False

	def f(node, res, arr):
		arr.append(node.data)
		if isLeaf(node):
			res.append(arr.copy())
			arr.pop()
			return
		if node.left:
			f(node.left, res, arr)
		if node.right:
			f(node.right, res, arr)
		arr.pop()
	res = []
	arr = []
	f(root, res, arr)
	return res


def Paths(root):
	res = []

	def sol(root, curr):
		if not root:
			return
		curr.append(root.data)
		if not root.left and (not root.right):
			res.append(curr.copy())
		sol(root.left, curr)
		sol(root.right, curr)
		curr.pop()
		return
	sol(root, [])
	return res


def fun(root, l, res):
	if root == None:
		return
	l.append(root.data)
	if root.left == None and root.right == None:
		res.extend(l)
		res.append('#')
	fun(root.left, l, res)
	fun(root.right, l, res)
	l.pop()

def Paths(root):
	if root == None:
		return
	(l, res) = ([], [])
	fun(root, l, res)
	(t, k) = ([], [])
	for i in res:
		if i == '#':
			k.append(t)
			t = []
		else:
			t.append(i)
	return k


def Paths(root):
	path = []
	dfs(root, path, [])
	return path

def dfs(root, path, ds):
	if not root:
		return
	ds.append(root.data)
	if not root.left and (not root.right):
		path.append(ds[:])
	l = dfs(root.left, path, ds)
	r = dfs(root.right, path, ds)
	ds.pop()


def Paths(root):
	k = Node([])
	k1 = Node([])

	def hh(root):
		if root == None:
			return
		k.data.append(root.data)
		if root.left == None and root.right == None:
			z = [i for i in k.data]
			k1.data.append(z)
		lh = hh(root.left)
		rh = hh(root.right)
		k.data.pop()
		return 1
	hh(root)
	return k1.data


def dfs(node, res, path):
	path.append(node)
	if node.left is None and node.right is None:
		newPath = []
		for n in path:
			newPath.append(n.data)
		res.append(newPath)
	if node.left:
		dfs(node.left, res, path)
		path.pop()
	if node.right:
		dfs(node.right, res, path)
		path.pop()

def Paths(root):
	res = []
	path = []
	dfs(root, res, path)
	return res


def answer(ans, path, root):
	if root is None:
		return
	path.append(root.data)
	if not root.right and (not root.left):
		ans.append(path.copy())
	if root.left:
		answer(ans, path, root.left)
	if root.right:
		answer(ans, path, root.right)
	path.pop()

def Paths(root):
	ans = []
	path = []
	answer(ans, path, root)
	return ans


def Paths(root):
	arr = []
	res = []

	def isLeaf(root):
		if root.left is None and root.right is None:
			return True
		return False

	def helper(root, arr, res):
		arr.append(root.data)
		if isLeaf(root):
			res.append(arr.copy())
			arr.pop()
			return
		if root.left is not None:
			helper(root.left, arr, res)
		if root.right is not None:
			helper(root.right, arr, res)
		arr.pop()
	helper(root, arr, res)
	return res


def Paths(root):

	def pr(root, pa, pl):
		if root == None:
			return
		if len(pa) > pl:
			pa[pl] = root.data
		else:
			pa.append(root.data)
		pl += 1
		if root.left == None and root.right == None:
			res.append(pa[:pl])
		else:
			pr(root.left, pa, pl)
			pr(root.right, pa, pl)
	p = []
	res = []
	pr(root, p, 0)
	return res


def solve(root, path, ans):
	if not root:
		return
	path.append(root.data)
	if not root.left and (not root.right):
		ans.append(path[:])
	solve(root.left, path, ans)
	solve(root.right, path, ans)
	path.pop()

def Paths(root):
	ans = []
	if not root:
		return ans
	path = []
	solve(root, path, ans)
	return ans


lis = []

def leaf(root, lis, res):
	if root == None:
		return
	res.append(root.data)
	if root.left == None and root.right == None:
		lis.append(res.copy())
	else:
		leaf(root.left, lis, res)
		leaf(root.right, lis, res)
	res.pop(-1)

def Paths(root):
	global lis
	lis = []
	leaf(root, lis, [])
	return lis


def Paths(root):
	ans = []

	def dfs(root, temp):
		nonlocal ans
		if not root:
			return
		temp.append(root.data)
		if not root.left and (not root.right):
			ans.append(temp[:])
		else:
			dfs(root.left, temp)
			dfs(root.right, temp)
		temp.pop()
		return
	dfs(root, [])
	return ans


def Paths(root):
	ans = []

	def roottoleaf(root, path):
		if not root:
			return
		path.append(root.data)
		if not root.left and (not root.right):
			ans.append(list(path))
		roottoleaf(root.left, list(path))
		roottoleaf(root.right, list(path))
	roottoleaf(root, [])
	return ans


def recur(root, ans, curr):
	if not root.left and (not root.right):
		ans.append(curr)
	if root.left:
		li = curr.copy()
		li.append(root.left.data)
		recur(root.left, ans, li)
	if root.right:
		li = curr.copy()
		li.append(root.right.data)
		recur(root.right, ans, li)

def Paths(root):
	ans = []
	recur(root, ans, [root.data])
	return ans


def Paths(root):

	def dfs(root, path, res):
		if root == None:
			return
		path.append(root.data)
		if root.left == None and root.right == None:
			res.append(path[:])
			path.pop()
			return
		if root.left != None:
			dfs(root.left, path, res)
		if root.right != None:
			dfs(root.right, path, res)
		path.pop()
	res = []
	dfs(root, [], res)
	return res


def Paths(root):

	def dfs(root, path, res):
		if root == None:
			return
		path.append(root.data)
		if root.left == None and root.right == None:
			temp = []
			for ele in path:
				temp.append(ele)
			res.append(temp)
			path.pop()
			return
		if root.left != None:
			dfs(root.left, path, res)
		if root.right != None:
			dfs(root.right, path, res)
		path.pop()
	res = []
	dfs(root, [], res)
	return res


def Paths(root):

	def dfs(node, path, res):
		if not node:
			return
		path.append(node.data)
		if not node.left and (not node.right):
			res.append(path[:])
		else:
			dfs(node.left, path, res)
			dfs(node.right, path, res)
		path.pop()
	res = []
	dfs(root, [], res)
	return res


def Paths(root):
	lst = []
	ans = []
	pathroottoleaf(root, ans, lst)
	return ans

def pathroottoleaf(root, ans, lst):
	if root == None:
		return False
	lst.append(root.data)
	if root.left == None and root.right == None:
		k = lst.copy()
		ans.append(k)
	lpath = pathroottoleaf(root.left, ans, lst)
	rpath = pathroottoleaf(root.right, ans, lst)
	if lpath == False and rpath == False:
		del lst[-1]
		return False


def Paths(root):

	def path(root, list, ans_list):
		if not root:
			return
		list.append(root.data)
		if not root.left and (not root.right):
			ans_list.append(list.copy())
			list.pop()
			return
		path(root.left, list, ans_list)
		path(root.right, list, ans_list)
		list.pop()
	ans_list = []
	path(root, [], ans_list)
	return ans_list


def Paths(root):
	ans = []

	def helper(root, list):
		if not root:
			return
		if not root.left and (not root.right):
			list.append(root.data)
			ans.append(list.copy())
			list.pop()
			return
		list.append(root.data)
		helper(root.left, list)
		helper(root.right, list)
		list.pop()
	helper(root, [])
	return ans


def Paths(root):
	ans_list = []

	def helper(root, list):
		if not root:
			return
		if not root.left and (not root.right):
			list.append(root.data)
			copy = list[:]
			ans_list.append(copy)
			return
		helper(root.left, list + [root.data])
		helper(root.right, list + [root.data])
	helper(root, [])
	return ans_list