#257

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Paths

Find all root-to-leaf paths in a binary tree using DFS and backtracking, constructing strings for each complete path efficiently.

string backtracking tree depth first search binary tree

Problem Statement

Given the root of a binary tree, return a list of strings representing all paths from the root node to each leaf node. Each path should be formatted by joining node values with '->'. A leaf node is defined as a node without left or right children. Ensure that your solution visits every node efficiently and maintains the current path during traversal.

For example, given a tree represented as [1,2,3,null,5], the correct output is ["1->2->5","1->3"]. Your solution must handle trees with up to 100 nodes and node values ranging from -100 to 100. Focus on tracking state during traversal to avoid missing paths or incorrectly formatting the strings.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = [1]

Output: ["1"]

Example details omitted.

Constraints

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

Solution Approach

Depth-First Search with String Tracking

Use DFS to traverse the tree recursively, appending the current node's value to a string path. When a leaf node is reached, add the completed path to the results list. This approach leverages the binary-tree traversal and state tracking pattern, ensuring each root-to-leaf path is captured correctly.

Backtracking to Maintain Path State

As you traverse, backtrack by removing the last node from the current path when returning from recursion. This prevents shared state corruption between different paths and avoids duplicate or incorrect string paths, a common failure mode in string construction for tree paths.

Iterative DFS Using a Stack

Optionally, implement DFS iteratively with a stack that stores pairs of nodes and their corresponding paths. Pop nodes one by one, push children with updated paths, and add complete paths to the results at leaves. This method also respects the pattern of maintaining traversal state explicitly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N) since every node is visited once, and constructing the path strings can also take O(N) per path. Space complexity is O(H) for recursion or stack storage, where H is the tree height, plus additional space for result strings.

What Interviewers Usually Probe

Pay attention to leaf node identification to avoid missing paths.
Ensure string paths are constructed incrementally, not concatenated at the end only.
Watch for off-by-one errors in backtracking or path formatting with '->'.

Common Pitfalls or Variants

Common pitfalls

Forgetting to backtrack when returning from recursion, leading to corrupted paths.
Incorrectly identifying leaf nodes, which may skip paths or add incomplete strings.
Using global or shared path state without copying, causing multiple paths to overlap incorrectly.

Follow-up variants

Return paths in reversed order or sorted lexicographically.
Generate paths as arrays of integers instead of string representations.
Handle trees where nodes may contain duplicate values but still track unique paths.

FAQ

What is the easiest way to track root-to-leaf paths in Binary Tree Paths?

Use depth-first search while maintaining the current path as a string, backtracking when returning from child nodes.

How do I handle leaf node detection to avoid missing paths?

Check that both left and right children are null before adding the current path to results to ensure only complete paths are stored.

Can I implement this problem iteratively instead of recursively?

Yes, by using a stack to store node-path pairs and popping nodes while extending paths, you can replicate DFS iteratively.

What are common mistakes when concatenating paths?

Forgetting to separate values with '->', or failing to backtrack the path string between branches, can corrupt output.

How does GhostInterview help with the binary-tree traversal and state tracking pattern?

It ensures that traversal state is properly maintained, paths are correctly added at leaves, and common backtracking errors are highlighted.

terminal

Solution

Solution 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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]:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            t.append(str(root.val))
            if root.left is None and root.right is None:
                ans.append("->".join(t))
            else:
                dfs(root.left)
                dfs(root.right)
            t.pop()

        ans = []
        t = []
        dfs(root)
        return ans

Continue Practicing

#988 smallest string starting from leaf #297 serialize and deserialize binary tree #113 path sum ii