089.md

257. Binary Tree Paths

Difficulty: 🟢 Easy

Given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.

Examples:

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 100 <= Node.val <= 100

Solutions

O(n) solution

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
        
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root: return 0

        def collect(node, current_path, paths):
            current_path.append(node.val)

            if not node.left and not node.right:
                paths.append("->".join(map(str,current_path)))

            if node.left:
                collect(node.left, current_path, paths)

            if node.right:
                collect(node.right, current_path, paths)

            current_path.pop()

        current_path, paths = [], []
        collect(root, current_path, paths)
        return paths

The given solution provides an approach to find all root-to-leaf paths in a binary tree.

Here is a step-by-step overview of the solution:

1. Define a recursive helper function collect that takes a node, a current path, and a list to store paths.
2. If the node is None, return 0.
3. Append the value of the current node to the current path.
4. If the node is a leaf (i.e., it has no left and right children), join the elements of the current path using " -> " as the separator and append the resulting string to the paths list.
5. Recursively call collect for the left child of the node.
6. Recursively call collect for the right child of the node.
7. Pop the last element (current node) from the current path to backtrack.

Finally, call the collect function for the root of the binary tree and return the list of paths.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once.

The space complexity is O(h), where h is the height of the binary tree. This is the maximum recursion depth.

Summary

The given solution provides an approach to find all root-to-leaf paths in a binary tree. It recursively traverses the tree, backtracking at leaf nodes to construct the paths. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the binary tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.