# Leetcode – Binary Tree Paths Solution in Python

## Introduction

Binary Tree Paths is a classic problem in LeetCode, frequently asked in coding interviews, which deals with binary trees and depth-first search. In this detailed article, we will explore the problem statement, discuss multiple approaches to solve it, and analyze their respective time and space complexities. We will provide Python implementations for each approach.

## 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.

### Input

• root: A reference to the root node of a binary tree.

### Output

• A list of strings, where each string represents a root-to-leaf path.

## Approach 1: Depth-First Search (DFS) with Recursion

This approach utilizes recursion to perform depth-first search through the binary tree.

1. Start DFS from the root node.
2. In the DFS, pass the current path as an argument.
3. For each node, append it to the current path.
4. If the current node is a leaf node, store the current path as one of the results.
5. Recur for the left and right children of the current node, passing the updated path.
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):
# Base case
if not root:
return []

# List to store the paths
paths = []

# Helper function for DFS
def dfs(node, path):
# Append the current node's value to the path
path += str(node.val)

# If it is a leaf node, add the path to the result
if not node.left and not node.right:
paths.append(path)
else:
path += "->" # Add the arrow for non-leaf nodes
# Recur for left and right children
if node.left:
dfs(node.left, path)
if node.right:
dfs(node.right, path)

# Start DFS from the root
dfs(root, "")

return paths

### Time Complexity

The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

### Space Complexity

The space complexity is O(H), where H is the height of the tree. This accounts for the maximum size of the recursive call stack during the DFS.

## Approach 2: Iterative Depth-First Search (DFS) with Stack

This approach uses an iterative DFS traversal using a stack, which simulates the behavior of the recursive approach.

1. Initialize a stack with the root node and its path.
2. Pop a node and its path from the stack.
3. If it’s a leaf node, store the path as one of the results.
4. Push the right and left children and their paths to the stack.
5. Repeat steps 2-4 until the stack is empty.
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):
# Base case
if not root:
return []

# List to store the paths
paths = []

# Stack for DFS
stack = [(root, str(root.val))]

# Iterate until the stack is empty
while stack:
# Pop a node and its path from the stack
node, path = stack.pop()

# If it's a leaf node, add the path to the result
if not node.left and not node.right:
paths.append(path)
# Push the right and left children and their paths to the stack
if node.right:
stack.append((node.right, path + "->" + str(node.right.val)))
if node.left:
stack.append((node.left, path + "->" + str(node.left.val)))

return paths

### Time Complexity

The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

### Space Complexity

The space complexity is O(H), where H is the height of the tree. This accounts for the maximum size of the stack during the DFS.

## Conclusion

We discussed the Binary Tree Paths problem on LeetCode and explored two different approaches to solving it – Recursive Depth-First Search and Iterative Depth-First Search using a stack. Both approaches have linear time complexity and are equally effective. The choice between recursive and iterative methods depends on personal preference and any specific constraints regarding space complexity or stack depth.