Binary Tree Paths (LeetCode 257)
You're handed a binary tree's root and asked to trace out every route from that root down to a leaf — a node with no children of its own. Report each route as a single string, its node values strung together with "->", and return the full collection in whatever order is convenient.
Worked Examples
root = [1,2,3,null,5]["1->2->5","1->3"]root = [1]["1"]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 100].-100 <= Node.val <= 100
Core Insight
Carry one mutable path buffer through the DFS. Append the node when a frame starts, record "->".join(path) only at a node with no children, recurse into both children, then pop before returning so the buffer is exactly as the caller left it.
Real-World Scenario & Production Applications
Listing every route through a decision tree, exporting every full category path in a product taxonomy, enumerating file paths from a directory root to each file.
Subproblems & Recurrence Decomposition3 Phases
Every real node appends its value to the one shared path buffer as its frame starts.
if not node:
return
path.append(str(node.val))| 1 | if not node: |
| 2 | return |
| 3 | path.append(str(node.val)) |
| 4 | if not node.left and not node.right: |
| 5 | paths.append("->".join(path)) |
| 6 | dfs(node.left) |
| 7 | dfs(node.right) |
| 8 | path.pop() |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Path Sum II records a path only when its sum hits a target. Binary Tree Paths removes the filter: every root-to-leaf walk is an answer. That makes it the cleanest possible look at the choose-explore-unchoose rhythm, with nothing else in the way.
🧵 The Analogy: A Museum Guide With One Tour Ticket
A guide walks visitors through a museum whose hallways branch like a tree. They carry a single ticket and stamp each room's name on it as they enter. Whenever they reach a dead-end room, they photocopy the ticket and file the copy: that copy is one complete tour. Then, walking back out of each room, they erase its stamp so the ticket is clean for the next hallway. One ticket serves every tour because every stamp is erased exactly when its room is left behind.
🔑 The Key Idea in the Code
"->".join(path) builds a brand-new string, so the recorded answer is a snapshot that later pop() calls can never change. The single shared buffer stays correct only because the append and the pop sit at the very start and the very end of the same frame.
Forgetting to unchoose: Forgetting
path.pop()leaks one branch's nodes into its sibling's paths ([1,2,3]wrongly yields"1->2->3").Recording at a half-leaf: Recording at any node with a missing child instead of only at true leaves adds half-finished paths (
[1,2]wrongly yields"1"as well).Negative values: Negative values need no special handling as long as each value is converted with
str()before joining.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
All root-to-leaf paths, returned as strings in any order.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: when a frame starts, path holds the root-to-parent values; when it returns, path is restored to that state.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Storing the list itself instead of a snapshot: later pops would change the recorded answer;
"->".join(path)makes a new string.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I keep one list
pathand a results list. Indfs(node)I return on None, appendstr(node.val), and if the node has no children I record"->".join(path). Then I recurse left and right and pop before returning, so every frame undoes its own append. It visits each node once; copying paths at the leaves makes it O(N·H) time, with O(H) extra space for the stack and buffer.
Complexity & Mathematical Proof
O(N · H)
Look at dfs(node): every node does O(1) work to append and pop its value. At each leaf, "->".join(path) copies a path of length at most H. With L leaves that adds L · O(H), and L ≤ N, so the total is O(N + L · H) ≤ O(N · H).
O(H) Auxiliary
The recursion stack and the shared path list both hold at most H entries (one per level of the current path). The returned paths list is output, not auxiliary space.
T(N, H) = O(N) + L · O(H) ≤ O(N · H)
Derivation Progression
O(N) node visits
Each node appends and pops its value once, O(1) each.
L leaves × O(H) join
Each finished root-to-leaf path is joined into a new string of length up to H.
O(N + L · H) ≤ O(N · H)
A balanced tree has about N/2 leaves of length log N: O(N log N).
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Number of leaves, one output path each (L ≤ N)
Memory Architecture & Bounds
O(H) recursion frames
O(H) shared path buffer
O(L · H) returned path strings
Boundary Best / Worst Cases
on a skewed chain (one leaf).
on a balanced tree.
when many leaves sit at depth close to .
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "all root-to-leaf paths", "return the paths in any order". Tree Backtracking (Choose-Explore-Unchoose): one shared path buffer walks the whole tree, and a copy of it is recorded every time the walk stands on a leaf.
. Time : every node is visited once, and each of the at most leaves copies a path of length up to .
Binary Tree Paths (LeetCode 257)
You're handed a binary tree's root and asked to trace out every route from that root down to a leaf — a node with no children of its own. Report each route as a single string, its node values strung together with "->", and return the full collection in whatever order is convenient.
Worked Examples
root = [1,2,3,null,5]["1->2->5","1->3"]root = [1]["1"]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 100].-100 <= Node.val <= 100
Core Insight
Carry one mutable path buffer through the DFS. Append the node when a frame starts, record "->".join(path) only at a node with no children, recurse into both children, then pop before returning so the buffer is exactly as the caller left it.
Real-World Scenario & Production Applications
Listing every route through a decision tree, exporting every full category path in a product taxonomy, enumerating file paths from a directory root to each file.
Subproblems & Recurrence Decomposition3 Phases
Every real node appends its value to the one shared path buffer as its frame starts.
if not node:
return
path.append(str(node.val))| 1 | if not node: |
| 2 | return |
| 3 | path.append(str(node.val)) |
| 4 | if not node.left and not node.right: |
| 5 | paths.append("->".join(path)) |
| 6 | dfs(node.left) |
| 7 | dfs(node.right) |
| 8 | path.pop() |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Path Sum II records a path only when its sum hits a target. Binary Tree Paths removes the filter: every root-to-leaf walk is an answer. That makes it the cleanest possible look at the choose-explore-unchoose rhythm, with nothing else in the way.
🧵 The Analogy: A Museum Guide With One Tour Ticket
A guide walks visitors through a museum whose hallways branch like a tree. They carry a single ticket and stamp each room's name on it as they enter. Whenever they reach a dead-end room, they photocopy the ticket and file the copy: that copy is one complete tour. Then, walking back out of each room, they erase its stamp so the ticket is clean for the next hallway. One ticket serves every tour because every stamp is erased exactly when its room is left behind.
🔑 The Key Idea in the Code
"->".join(path) builds a brand-new string, so the recorded answer is a snapshot that later pop() calls can never change. The single shared buffer stays correct only because the append and the pop sit at the very start and the very end of the same frame.
Forgetting to unchoose: Forgetting
path.pop()leaks one branch's nodes into its sibling's paths ([1,2,3]wrongly yields"1->2->3").Recording at a half-leaf: Recording at any node with a missing child instead of only at true leaves adds half-finished paths (
[1,2]wrongly yields"1"as well).Negative values: Negative values need no special handling as long as each value is converted with
str()before joining.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
All root-to-leaf paths, returned as strings in any order.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: when a frame starts, path holds the root-to-parent values; when it returns, path is restored to that state.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Storing the list itself instead of a snapshot: later pops would change the recorded answer;
"->".join(path)makes a new string.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I keep one list
pathand a results list. Indfs(node)I return on None, appendstr(node.val), and if the node has no children I record"->".join(path). Then I recurse left and right and pop before returning, so every frame undoes its own append. It visits each node once; copying paths at the leaves makes it O(N·H) time, with O(H) extra space for the stack and buffer.
Complexity & Mathematical Proof
O(N · H)
Look at dfs(node): every node does O(1) work to append and pop its value. At each leaf, "->".join(path) copies a path of length at most H. With L leaves that adds L · O(H), and L ≤ N, so the total is O(N + L · H) ≤ O(N · H).
O(H) Auxiliary
The recursion stack and the shared path list both hold at most H entries (one per level of the current path). The returned paths list is output, not auxiliary space.
T(N, H) = O(N) + L · O(H) ≤ O(N · H)
Derivation Progression
O(N) node visits
Each node appends and pops its value once, O(1) each.
L leaves × O(H) join
Each finished root-to-leaf path is joined into a new string of length up to H.
O(N + L · H) ≤ O(N · H)
A balanced tree has about N/2 leaves of length log N: O(N log N).
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Number of leaves, one output path each (L ≤ N)
Memory Architecture & Bounds
O(H) recursion frames
O(H) shared path buffer
O(L · H) returned path strings
Boundary Best / Worst Cases
on a skewed chain (one leaf).
on a balanced tree.
when many leaves sit at depth close to .
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "all root-to-leaf paths", "return the paths in any order". Tree Backtracking (Choose-Explore-Unchoose): one shared path buffer walks the whole tree, and a copy of it is recorded every time the walk stands on a leaf.
. Time : every node is visited once, and each of the at most leaves copies a path of length up to .