Today problem of the day on geeks for geeks potd is Root to Leaf Paths on gfg 8 May 2024. This problem is an medium level questions on tree data structures. It is one of the widely asked questions by some of dream companies like Amazon and Paytm and other highly anticipated tech giants and top IT firms.

Please do not directly look for the solution for todays geeks for geeks problem of the day, instead try to learn the basic concepts about binary trees and try to define an approach that you would take to solve root to leaf paths problem using python or your favorite programming language. Have look into solution for root to leaf paths only if you are stuck.

## gfg potd today solution in Python

To find all possible paths from the root node to all leaf nodes (the ending nodes in a tree structure which further has no child nodes) in a binary tree, we can use a depth-first search (DFS) approach with backtracking. Let’s have the Python code to implement the `Paths`

function:

`from typing import Optional, List`

class Solution:

def Paths(self, root: Optional['Node']) -> List[List[int]]:

paths = []

self.dfs(root, [], paths)

return paths

def dfs(self, node: Optional['Node'], current_path: List[int], paths: List[List[int]]) -> None:

if not node:

return

current_path.append(node.data)

# If the current node is a leaf node, add the current path to the result

if not node.left and not node.right:

paths.append(current_path[:])

# Recursively explore the left and right subtrees

self.dfs(node.left, current_path, paths)

self.dfs(node.right, current_path, paths)

# Backtrack by removing the current node from the current path

current_path.pop()

Let’s try to understand how it works!

- The
`Paths`

function initializes an empty list`paths`

to store all the paths from the root to leaf nodes. - It calls the helper function
`dfs`

with the root node, an empty`current_path`

list, and the`paths`

list. - The
`dfs`

function recursively explores the binary tree, starting from the given`node`

. - If the
`node`

is`None`

, it returns, as there is no path to explore. - Otherwise, it appends the
`node.data`

to the`current_path`

list. - If the current
`node`

is a leaf node (i.e., it has no left or right child), it means we have found a complete path from the root to a leaf node. We append a copy of the`current_path`

to the`paths`

list. - If the current node is not a leaf node, we recursively call the
`dfs`

function for the left and right subtrees, passing the`current_path`

and`paths`

lists. - After exploring the left and right subtrees, we backtrack by removing the last element from the
`current_path`

list using`current_path.pop()`

.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The auxiliary space complexity is O(height of the tree) due to the recursive calls on the call stack, plus O(n) for storing the paths in the `paths`

list.