257. Binary Tree Paths | LeetCode Easy | Python Solution | Binary Tree, DFS, String, Backtracking

Опубликовано: 01 Январь 2023
на канале: Shaheer Shukur

1,966

Leetcode easy problem 257. Binary Tree Paths, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/binary-...
Solution (Python Code): https://github.com/shaheershukur/Leet...

#leetcode #python #solution

Problem Statement:
Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given a binary tree and we need to find out all the root to leaf paths.
we know that, a binary tree is a tree in which each node can have at most 2 children.
ie, each node can have at most a left child and a right child.

in a tree, the topmost node, or the node that doesn't have any parent is called the root node of the tree.
and, the bottommost node,or the node that doesn't have any children is called the leaf node.

we need to find out all the paths from the root node to the leaf nodes.
for example, for this tree, we have the paths "1,2,5", "1,3,6" and "1,3,7".

to solve this, what we can do is, first we will start the traversal from the root node.
and also, during traversal, at each node, we will be recording the path we have taken.
now, from this node, we will check whether its having a left node or a right node.

since its having a left node, we will first continue the traversal in that path.
now, at this node, we do not have a left node.
but we do have a right node.
so, we will continue the traversal in that path.

now, at this node, we neither have a left node nor a right node.
that means, we are currently at a leaf node, and therefore we can stop the traversal and store the path to the result.

now coming back to node 1, we can now traverse through the right node.
from this node, we can continue the traversal through the left node.

at this node, we dont have a left or right node.
that means, we have reached a leaf node and therefore we can stop the traversal and store the path to the result.

now, coming back to node 3, we can now traverse through the right node.
at this node, we dont have a left or right node.
that means, we have reached a leaf node and therefore we can stop the traversal and store the path to the result.

finally, this is the list of all the paths from the root node to the leaf nodes.

now lets code the solution.

we will create an array for storing the result, and at last, we will be returning it.

for traversing through the tree, we write a seperate function.

we will start the traversal from the root node, and initially the path will be starting with the root node.
since its given in the problem that there will be at least one node in the given tree, we dont have to put any null checks for the root node.

inside the function, we will check whether the current node has a left node.
if it has a left node, then we will call the function recursively by passing the left node and adding the left node value to the path.

likewise, if the current node has a right node, we will call the function recursively by passing the right node and adding the right node value to the path.

and at the beggining of the function, we must check whether the current node is a leaf node.
if it neither have a left node nor a right node, then its a leaf node, and therefore we can store the path to the result and return from the function.
before adding the path to the result, we will join together the string elements with this arrow string.