LeetCode 257: Binary Tree Paths Solution in Python – A Step-by-Step Guide

Picture yourself exploring a tree, starting at the top and tracing every possible route down to the leaves, writing down the numbers you see along the way—like "1->2->5" or "1->3". That’s the fun task of LeetCode 257: Binary Tree Paths! This easy-level problem asks you to find all paths from the root to the leaf nodes in a binary tree and list them as strings. Using Python, we’ll explore two solutions: the Best Solution, a depth-first search (DFS) with path tracking, and an Alternative Solution, a breadth-first search (BFS) with a queue. With detailed examples, clear code, and easy-to-follow explanations—especially for the best solution—this guide will help you navigate trees and sharpen your coding skills. Let’s start walking those paths!

What Is LeetCode 257: Binary Tree Paths?

In LeetCode 257: Binary Tree Paths, you’re given the root of a binary tree, and your goal is to return a list of strings, where each string shows a path from the root to a leaf node, with node values separated by "->". A leaf node is one with no children. This problem introduces tree traversal in a practical way, related to challenges like LeetCode 94: Binary Tree Inorder Traversal, but focuses on collecting full paths instead of just visiting nodes.

Problem Statement

Input: A binary tree root node.
Output: A list of strings, each representing a root-to-leaf path.
Rules: Paths go from root to leaf; use "->" between values; include all possible paths.

Constraints

Number of nodes: 1 to 100.
Node values: -100 to 100.

Examples

Input: Tree with root = 1, left = 2 (right = 5), right = 3

Text representation:

Root: 1
Left: 2

Right: 5

Right: 3

Output: ["1->2->5", "1->3"]

Input: Tree with root = 1

Text representation:

Root: 1

Output: ["1"]

Understanding the Problem: Tracing Tree Paths

To solve LeetCode 257: Binary Tree Paths in Python, we need to find every route from the root to a leaf in a binary tree and turn each route into a string like "root->child->leaf". A binary tree has up to two children per node (left and right), and a leaf is a node with no left or right child. A simple way—manually listing paths—works for tiny trees but gets messy fast. We’ll use two methods: 1. Best Solution (DFS with Path Tracking): O(n) time—quick and natural for trees. 2. Alternative Solution (BFS with Queue): O(n) time—another way to explore.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: DFS with Path Tracking

Why This Is the Best Solution

The depth-first search (DFS) with path tracking approach is the top pick for LeetCode 257 because it runs in O(n) time—where n is the number of nodes—and follows the tree’s natural flow, diving deep down each path to the leaves. It uses a small amount of extra space and feels intuitive once you see it, making it a great fit for this problem.

How It Works

Think of this solution as a treasure hunt: you start at the root with a little notebook, writing down each number you see as you walk down a path. When you reach a leaf, you save the full path you’ve written. Then you back up, erase the last step, and try another direction. Here’s how it works, step-by-step, explained in a way that’s easy to follow:

Step 1: Start at the Root:

You’re at the top node (e.g., 1), and your notebook starts with just "1".

Step 2: Explore with DFS:

DFS means “go deep first.” Look at the left child:

If there’s a left child (e.g., 2), add "->2" to your notebook ("1->2").
Keep going left or right from there.

If you hit a leaf (no children), save the path in your notebook as a string.

Step 3: Backtrack:

When you finish a path, go back up, erase the last number, and try the right child.
For example, after "1->2->5", back up to "1->2", then try the right side.

Step 4: Use a Helper Function:

Write a small function that takes the current node and the path so far.
It adds the node’s value, checks for leaves, and explores children.

Step 5: Collect All Paths:

Keep a list to store every path you find when you reach a leaf.

It’s like wandering through a maze, jotting down your route, and shouting “Found one!” when you reach the end!

Step-by-Step Example

Example: Tree with root = 1, left = 2 (right = 5), right = 3

Text Representation:

Root: 1
Left: 2

Right: 5

Right: 3

Step 1: Start at Root:

Path = "1", Result = [].

Step 2: Go Left:

At 2, Path = "1->2".
No left child, go right to 5.

Step 3: Reach Leaf 5:

At 5, Path = "1->2->5".
No children (leaf), add "1->2->5" to Result.

Step 4: Backtrack to 1:

Back to 1, Path = "1".
Go right to 3.

Step 5: Reach Leaf 3:

At 3, Path = "1->3".
No children, add "1->3" to Result.

Step 6: Finish:

Result = ["1->2->5", "1->3"].

Result: ["1->2->5", "1->3"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

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: TreeNode) -> List[str]:
        # Step 1: Set up our path collection
        result = []  # Where we’ll store all paths

        # Step 2: Helper function to explore the tree
        def dfs(node, path):
            # If there’s no node, stop here
            if not node:
                return

            # Add this node’s value to the path
            if not path:  # First node (root)
                path = str(node.val)
            else:  # Add with arrow
                path += "->" + str(node.val)

            # Step 3: Check if it’s a leaf
            if not node.left and not node.right:
                result.append(path)  # Save the full path
                return

            # Step 4: Explore left and right children
            dfs(node.left, path)
            dfs(node.right, path)

        # Step 5: Start the adventure at the root
        dfs(root, "")
        return result

Time Complexity: O(n)—visits each node once.
Space Complexity: O(h)—where h is the tree height, for the recursion stack.

This solution is like a trusty guide—leading you down every path to the treasure!

Alternative Solution: BFS with Queue

Why an Alternative Approach?

The breadth-first search (BFS) with queue method explores the tree level by level, like checking all the rooms on one floor before moving down. It’s another way to find paths, using a queue to keep track of nodes and their paths so far, offering a different perspective on the problem.

How It Works

Imagine you’re mailing letters from the root to every leaf, passing them along level by level. Each letter carries the path it’s taken so far, and when it reaches a leaf, you save it. Here’s how it works, step-by-step:

Step 1: Start with a Queue:

Put the root and its path ("1") in a queue.

Step 2: Explore Level by Level:

Take a node from the queue, add its children with updated paths.
If a node is a leaf, save its path.

Step 3: Keep Going:

Repeat until the queue is empty.

It’s like sending explorers out in waves, collecting messages from the farthest points!

Step-by-Step Example

Example: Tree with root = 1, left = 2 (right = 5), right = 3

Text Representation:

Root: 1
Left: 2

Right: 5

Right: 3

Step 1: Queue Starts:

Queue = [(1, "1")], Result = [].

Step 2: Process Level 1:

Dequeue (1, "1"):

Left 2: Queue += (2, "1->2").
Right 3: Queue += (3, "1->3").

Queue = [(2, "1->2"), (3, "1->3")].

Step 3: Process Level 2:

Dequeue (2, "1->2"):

Right 5: Queue += (5, "1->2->5").

Dequeue (3, "1->3"):

Leaf, add "1->3" to Result.

Queue = [(5, "1->2->5")].

Step 4: Process Level 3:

Dequeue (5, "1->2->5"):

Leaf, add "1->2->5" to Result.

Queue = [].

Result: ["1->2->5", "1->3"].

Code for BFS Approach

from collections import deque

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: TreeNode) -> List[str]:
        # Step 1: Handle empty tree
        if not root:
            return []

        # Step 2: Set up queue and result
        result = []
        queue = deque([(root, str(root.val))])

        # Step 3: Explore level by level
        while queue:
            node, path = queue.popleft()
            # If it’s a leaf, save the path
            if not node.left and not node.right:
                result.append(path)
            # Add children with updated paths
            if node.left:
                queue.append((node.left, path + "->" + str(node.left.val)))
            if node.right:
                queue.append((node.right, path + "->" + str(node.right.val)))

        return result

Time Complexity: O(n)—visits each node once.
Space Complexity: O(w)—where w is the maximum width of the tree.

It’s a solid alternative, exploring wide instead of deep.

Comparing the Two Solutions

Best Solution (DFS):

Pros: O(n) time, O(h) space, tree-friendly.
Cons: Recursion might feel tricky at first.

Alternative Solution (BFS):

Pros: O(n) time, level-by-level view.
Cons: O(w) space, can grow wider.

DFS wins for simplicity and space.

Additional Examples and Edge Cases

Single Node

Root: 1 → ["1"]

Left-Only Tree

Root: 1, Left: 2 → ["1->2"]

Full Tree

Root: 1, Left: 2, Right: 3 → ["1->2", "1->3"]

Both handle these smoothly.

Complexity Breakdown

DFS:

Time: O(n)—one pass.
Space: O(h)—stack.

BFS:

Time: O(n)—one pass.
Space: O(w)—queue.

DFS is leaner for tall trees.

Key Takeaways

DFS: Dive deep, track paths naturally.
BFS: Explore wide, use a queue.
Paths: Build strings as you go.
Python Tip: Strings and lists team up—see [Python Basics](/python/basics).

Final Thoughts: Explore Paths Like a Pro

LeetCode 257: Binary Tree Paths in Python is a delightful tree adventure. The DFS solution flows smoothly down each path, while BFS offers a wide-angle view. Want more? Try LeetCode 94: Inorder Traversal or LeetCode 104: Maximum Depth. Ready to explore? Head to Solve LeetCode 257 on LeetCode and trace those paths today!