LeetCode 257: Binary Tree Paths

Problem Restatement

We are given the root of a binary tree.

We need to return all paths from the root to every leaf node.

A leaf node is a node with no left child and no right child.

Each path must be returned as a string using "->" between node values.

For example, this path:

1
 \
  2
   \
    5

becomes:

"1->2->5"

The problem asks for all root-to-leaf paths in any order. The tree has between 1 and 100 nodes, and each node value is between -100 and 100.

Input and Output

Example function shape:

def binaryTreePaths(root: Optional[TreeNode]) -> list[str]:
    ...

Examples

Example 1:

root = [1, 2, 3, None, 5]

Tree:

    1
   / \
  2   3
   \
    5

There are two root-to-leaf paths.

The first path is:

"1->2->5"

The second path is:

"1->3"

Answer:

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

Example 2:

root = [1]

The root itself is also a leaf.

Answer:

["1"]

First Thought: Traverse Every Path

A binary tree path starts at the root and moves down through child pointers.

So the natural approach is depth-first search.

While walking down the tree, we keep the current path.

When we reach a leaf, the current path is complete, so we convert it into a string and add it to the answer.

Problem With Building Strings Too Early

One simple method is to pass a string into every recursive call.

For example:

dfs(node.left, path + "->" + str(node.left.val))

This works, but it repeatedly creates new strings.

For small input this is fine. But a cleaner general technique is to keep a list of path values, then join the list only when we reach a leaf.

That gives a standard backtracking shape.

Key Insight

At any node, the current path contains all values from the root to that node.

For example, in this tree:

    1
   /
  2
   \
    5

when DFS reaches node 5, the path list is:

["1", "2", "5"]

Since 5 is a leaf, we convert it into:

"1->2->5"

Then we backtrack by removing 5, so the path can be reused for other branches.

Algorithm

Use DFS with a mutable path list.

At each node:

1. Add the current node value to path.
2. If the node is a leaf:
   • Join path using "->".
   • Add the joined string to ans.
3. Otherwise:
   • DFS into the left child.
   • DFS into the right child.
4. Remove the current node value from path.

The final pop is the backtracking step.

Walkthrough

Use this tree:

    1
   / \
  2   3
   \
    5

Start at node 1.

path = ["1"]

Move left to node 2.

path = ["1", "2"]

Node 2 is not a leaf because it has a right child.

Move right to node 5.

path = ["1", "2", "5"]

Node 5 is a leaf.

Add:

"1->2->5"

Backtrack to node 2, then backtrack to node 1.

Now move right to node 3.

path = ["1", "3"]

Node 3 is a leaf.

Add:

"1->3"

The final answer is:

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

Correctness

The DFS visits every node reachable from the root.

During each recursive call, path contains exactly the node values on the current root-to-current-node path. This is true because we append the current node before exploring its children, and remove it after finishing that node.

When DFS reaches a leaf, the current path starts at the root and ends at that leaf. So joining the path produces a valid root-to-leaf path string.

Every root-to-leaf path is found because DFS explores both left and right children of every non-leaf node.

No invalid path is added because the algorithm appends to ans only when the current node has no children.

Therefore the algorithm returns exactly all root-to-leaf paths.

Complexity

Let n be the number of nodes and h be the height of the tree.

The output itself also takes space proportional to the total length of all returned path strings.

Implementation

from typing import Optional, List

# 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]:
        ans = []
        path = []

        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            path.append(str(node.val))

            if node.left is None and node.right is None:
                ans.append("->".join(path))
            else:
                dfs(node.left)
                dfs(node.right)

            path.pop()

        dfs(root)
        return ans

Code Explanation

We store completed path strings in:

ans = []

We store the current root-to-node path in:

path = []

The DFS ignores empty nodes:

if node is None:
    return

When we enter a node, we add its value:

path.append(str(node.val))

We store strings instead of integers because the final output uses string joining.

A node is a leaf when both children are missing:

if node.left is None and node.right is None:

At a leaf, the path is complete:

ans.append("->".join(path))

For a non-leaf node, we continue searching:

dfs(node.left)
dfs(node.right)

After finishing the current node, we remove it from the path:

path.pop()

This restores the path before returning to the parent.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def normalize(paths: list[str]) -> list[str]:
    return sorted(paths)

def run_tests():
    s = Solution()

    root = TreeNode(
        1,
        TreeNode(2, None, TreeNode(5)),
        TreeNode(3),
    )
    assert normalize(s.binaryTreePaths(root)) == normalize(["1->2->5", "1->3"])

    root = TreeNode(1)
    assert s.binaryTreePaths(root) == ["1"]

    root = TreeNode(1, TreeNode(2), None)
    assert s.binaryTreePaths(root) == ["1->2"]

    root = TreeNode(1, None, TreeNode(3))
    assert s.binaryTreePaths(root) == ["1->3"]

    root = TreeNode(-1, TreeNode(-2), TreeNode(3))
    assert normalize(s.binaryTreePaths(root)) == normalize(["-1->-2", "-1->3"])

    print("all tests passed")

run_tests()

Test meaning: