This problem requires generating every path from the root to leaf nodes in a binary tree. Using depth-first search combined with backtracking, you can traverse the tree while maintaining the current path as a string. GhostInterview guides you in correctly tracking state, avoiding common off-by-one errors, and producing all paths in any valid order efficiently.
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.
How GhostInterview Helps
- Automatically tracks your traversal state and highlights missing or duplicated paths.
- Provides step-by-step guidance on string path construction during DFS or backtracking.
- Identifies typical off-by-one or leaf-detection mistakes before submission, saving debugging time.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Binary Tree Paths instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Binary Tree Paths from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the lexicographically smallest string from a leaf to root using binary-tree traversal and careful state tracking.
Open problem page#297 Serialize and Deserialize Binary TreeThis problem asks to serialize and deserialize a binary tree, requiring an efficient approach to handle traversal and state tracking.
Open problem page#113 Path Sum IIFind all root-to-leaf paths in a binary tree where the sum of node values equals a given target using DFS backtracking.
Open problem page