LeetCode 257 - Binary Tree Paths

LeetCode Problem 257

Difficulty: 🟢 Easy
Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to return every path from the root of a binary tree to each leaf node. A root-to-leaf path is formed by starting at the root node and continuously moving downward through child nodes until reaching a node that has no children.

The input is the root node of a binary tree. Each node contains an integer value and pointers to its left and right children. The tree can contain anywhere from 1 to 100 nodes, and node values range from -100 to 100.

The output should be a list of strings, where each string represents one complete root-to-leaf path. The values along the path are connected using the "->" separator. For example, the path from node 1 to node 2 to node 5 becomes "1->2->5".

A key detail is that only root-to-leaf paths should be included. Intermediate paths are not valid unless they end at a leaf node. A leaf node is defined as a node with neither a left child nor a right child.

The constraints are small, only up to 100 nodes, which means even recursive depth-first traversal is completely safe. Since every node must potentially appear in an output path, any valid solution will need to visit all nodes at least once.

Several edge cases are important to recognize early:

• A tree with only one node should return a single path containing just that node’s value.
• Trees may be skewed entirely left or entirely right, creating paths with maximum possible depth.
• Node values can be negative, so path construction must correctly handle negative numbers as strings.
• Some nodes may have only one child, meaning traversal logic cannot assume both children exist.

Approaches

Brute Force Approach

A brute-force solution would generate all possible paths from the root to every node, then filter out only the paths that end at leaf nodes. One way to do this is to repeatedly copy the current path list during traversal and store every partial path encountered.

This works because every possible root-to-node path is explored, guaranteeing that all root-to-leaf paths are eventually discovered. However, it performs unnecessary work because paths that do not end at leaves are still constructed and stored temporarily.

Additionally, repeatedly copying path arrays or strings at every recursive call introduces extra overhead. Although the constraints are small enough that this would still pass, it is not the cleanest or most efficient strategy.

Optimal Approach

The optimal solution uses depth-first search with backtracking. The key observation is that a root-to-leaf path naturally corresponds to a traversal path in DFS.

As we recursively move down the tree, we maintain the current path. When we reach a leaf node, we know the current path is complete, so we convert it into the required string format and add it to the answer.

This approach avoids unnecessary work because paths are only finalized when reaching leaves. Each node is visited exactly once, making the traversal efficient and straightforward.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(N²)	Repeatedly copies partial paths during traversal
Optimal	O(N²)	O(N)	DFS with backtracking, each node visited once

The time complexity becomes O(N²) in the worst case because constructing output strings requires copying path contents, especially in skewed trees where path lengths approach N.

Algorithm Walkthrough

1. Start a depth-first traversal from the root node.

We use DFS because every root-to-leaf path corresponds naturally to one traversal branch in the tree. DFS allows us to explore one path completely before moving to another. 2. Maintain a list representing the current path.

As we visit nodes, we append the current node’s value to the path list. This list always represents the exact sequence of nodes from the root to the current node. 3. Check whether the current node is a leaf.

A node is a leaf if both its left and right children are None. When we reach a leaf, the current path is complete and valid. 4. Convert the path into the required string format.

We transform the path values into strings and join them using "->". This produces the required output representation. 5. Store the completed path in the result list.

Every time we encounter a leaf node, we add the constructed path string to the final answer. 6. Recursively traverse the left subtree.

If a left child exists, continue DFS while preserving the current path state. 7. Recursively traverse the right subtree.

If a right child exists, continue DFS similarly. 8. Backtrack after processing children.

Remove the current node from the path list before returning to the parent call. This ensures the path list correctly reflects the traversal state for sibling branches.

Why it works

The algorithm maintains the invariant that the path list always contains the exact sequence of node values from the root to the current node. DFS guarantees every root-to-leaf route is explored exactly once. When a leaf is reached, the stored path is therefore a valid root-to-leaf path, and because every leaf is visited, all valid paths are included in the final answer.

Python Solution

# 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

from typing import List, Optional

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []

        def dfs(node: TreeNode, path: List[str]) -> None:
            path.append(str(node.val))

            # Leaf node
            if not node.left and not node.right:
                result.append("->".join(path))
            else:
                if node.left:
                    dfs(node.left, path)

                if node.right:
                    dfs(node.right, path)

            # Backtrack
            path.pop()

        dfs(root, [])
        return result

The solution begins by initializing an empty result list that will store all completed path strings.

The nested dfs function performs recursive depth-first traversal. It accepts the current node and the current path list.

At the beginning of each call, the current node’s value is appended to the path. This maintains the invariant that the path list always represents the current traversal route from the root.

The algorithm then checks whether the node is a leaf. If both children are absent, the current path is complete. The values are joined together with "->" and added to the result list.

If the node is not a leaf, recursion continues into any existing children.

Finally, path.pop() performs backtracking. This removes the current node before returning to the parent call so the path remains correct for future traversal branches.

Because the recursion explores every root-to-leaf branch exactly once, all valid paths are collected.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "strconv"
import "strings"

func binaryTreePaths(root *TreeNode) []string {
    result := []string{}

    var dfs func(node *TreeNode, path []string)

    dfs = func(node *TreeNode, path []string) {
        path = append(path, strconv.Itoa(node.Val))

        // Leaf node
        if node.Left == nil && node.Right == nil {
            result = append(result, strings.Join(path, "->"))
            return
        }

        if node.Left != nil {
            dfs(node.Left, path)
        }

        if node.Right != nil {
            dfs(node.Right, path)
        }
    }

    dfs(root, []string{})
    return result
}

The Go solution follows the same DFS strategy as the Python version. The primary difference is how slices behave in Go.

Instead of explicit backtracking with pop, Go slices are passed by value as slice headers. Appending creates a new slice state for recursive calls, so separate traversal branches do not interfere with one another.

Node values are converted to strings using strconv.Itoa, and completed paths are joined using strings.Join.

Nil checks are used instead of Python’s None.

Worked Examples

Example 1

Input:

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

Tree structure:

      1
     / \
    2   3
     \
      5

Traversal process:

Step	Current Node	Current Path	Action
1	1	["1"]	Continue DFS
2	2	["1", "2"]	Continue DFS
3	5	["1", "2", "5"]	Leaf found, add "1->2->5"
4	3	["1", "3"]	Leaf found, add "1->3"

Final result:

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

Example 2

Input:

root = [1]

Tree structure:

1

Traversal process:

Step	Current Node	Current Path	Action
1	1	["1"]	Leaf found immediately

Final result:

["1"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N²)	Each node is visited once, but path string creation can cost O(N) in skewed trees
Space	O(N)	Recursive call stack and current path storage

The DFS traversal itself is linear because every node is processed exactly once. However, constructing path strings requires copying characters. In the worst case of a completely skewed tree, there can be O(N) paths of length O(N), producing O(N²) total string construction work.

The auxiliary space complexity is O(N) due to recursion depth and the current path list. In a balanced tree, recursion depth is closer to O(log N), but worst-case skewed trees require O(N) stack space.

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.right = TreeNode(5)

assert sorted(solution.binaryTreePaths(root1)) == sorted([
    "1->2->5",
    "1->3"
])  # Standard multi-path tree

# Example 2
root2 = TreeNode(1)

assert solution.binaryTreePaths(root2) == [
    "1"
]  # Single-node tree

# Left-skewed tree
root3 = TreeNode(1)
root3.left = TreeNode(2)
root3.left.left = TreeNode(3)

assert solution.binaryTreePaths(root3) == [
    "1->2->3"
]  # Only left children

# Right-skewed tree
root4 = TreeNode(1)
root4.right = TreeNode(2)
root4.right.right = TreeNode(3)

assert solution.binaryTreePaths(root4) == [
    "1->2->3"
]  # Only right children

# Tree with negative values
root5 = TreeNode(-1)
root5.left = TreeNode(-2)
root5.right = TreeNode(3)

assert sorted(solution.binaryTreePaths(root5)) == sorted([
    "-1->-2",
    "-1->3"
])  # Handles negative numbers correctly

# Balanced tree with multiple leaves
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.right = TreeNode(3)
root6.left.left = TreeNode(4)
root6.left.right = TreeNode(5)
root6.right.left = TreeNode(6)
root6.right.right = TreeNode(7)

assert sorted(solution.binaryTreePaths(root6)) == sorted([
    "1->2->4",
    "1->2->5",
    "1->3->6",
    "1->3->7"
])  # Multiple root-to-leaf paths

Test	Why
[1,2,3,null,5]	Standard example with multiple paths
[1]	Validates single-node edge case
Left-skewed tree	Tests deep recursion on one side
Right-skewed tree	Ensures traversal works symmetrically
Negative values	Confirms string formatting handles negatives
Full balanced tree	Verifies collection of many leaf paths

Edge Cases

A single-node tree is one of the most important edge cases. Since the root is also a leaf, the algorithm must immediately recognize that the path is complete. Some incorrect implementations attempt to recurse before checking leaf conditions, which can lead to missing the only valid path. This implementation correctly checks for a leaf immediately after adding the node to the path.

Skewed trees are another important case. A tree that behaves like a linked list can create recursion depth equal to the number of nodes. Incorrect backtracking logic often appears in these scenarios because there are no sibling branches to expose path corruption bugs. The implementation avoids this issue by always removing the current node from the path before returning.

Trees containing negative values can also introduce subtle formatting bugs. Since the output format is string-based, the algorithm must convert integers properly without losing the negative sign. Using str(node.val) in Python and strconv.Itoa(node.Val) in Go guarantees negative numbers are represented correctly.

Nodes with only one child are another common source of mistakes. Some implementations incorrectly assume both children exist and attempt unnecessary recursion. This solution explicitly checks whether each child exists before recursing, ensuring traversal remains correct for sparse trees.