Binary Tree Paths (LeetCode 257)
Choose-Explore-Unchoose With One Shared Buffer: Record Every Root-to-Leaf Path
You are given the root of a binary tree. Return every path that starts at the root and ends at a leaf (a node with no children), written as the node values joined by "->". The paths may be returned in any order.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return |
| 2 | path.append(str(node.val)) |
| 3 | if not node.left and not node.right: paths.append("->".join(path)) |
| 4 | dfs(node.left); dfs(node.right) |
| 5 | path.pop() |
Target: Binary Tree Paths (LeetCode 257). The buffer grows by exactly this node on entry
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Path Sum II (§4.8) 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.
🪄 Breaking Down the Code's "Magic Trick"
def dfs(node): if not node: return path.append(str(node.val)) # choose: stamp this room if not node.left and not node.right: paths.append("->".join(path)) # a leaf: file a copy of the finished tour dfs(node.left) # explore dfs(node.right) path.pop() # unchoose: erase the stamp on the way out "->".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.
💡 Summary
When a tree problem asks you to list or examine every root-to-leaf path, carry one mutable path buffer, record a snapshot at each true leaf, and undo your own append before returning. The same frame that chooses a node must also unchoose it.
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
You will see how one shared path buffer, appended on entry and popped on exit, records every root-to-leaf path.
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
Forgetting
path.pop(): one branch's nodes leak into the sibling's paths.Recording when only one child is missing: half-finished paths such as
"1"in[1,2]get recorded.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.
So: append the node, record a joined snapshot at a true leaf, explore both children, pop.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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 .
Forgetting path.pop() leaks one branch's nodes into its sibling's paths ([1,2,3] wrongly yields "1->2->3"). 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 need no special handling as long as each value is converted with str() before joining.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
Binary Tree Paths (LeetCode 257)
Choose-Explore-Unchoose With One Shared Buffer: Record Every Root-to-Leaf Path
You are given the root of a binary tree. Return every path that starts at the root and ends at a leaf (a node with no children), written as the node values joined by "->". The paths may be returned in any order.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return |
| 2 | path.append(str(node.val)) |
| 3 | if not node.left and not node.right: paths.append("->".join(path)) |
| 4 | dfs(node.left); dfs(node.right) |
| 5 | path.pop() |
Target: Binary Tree Paths (LeetCode 257). The buffer grows by exactly this node on entry
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Path Sum II (§4.8) 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.
🪄 Breaking Down the Code's "Magic Trick"
def dfs(node): if not node: return path.append(str(node.val)) # choose: stamp this room if not node.left and not node.right: paths.append("->".join(path)) # a leaf: file a copy of the finished tour dfs(node.left) # explore dfs(node.right) path.pop() # unchoose: erase the stamp on the way out "->".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.
💡 Summary
When a tree problem asks you to list or examine every root-to-leaf path, carry one mutable path buffer, record a snapshot at each true leaf, and undo your own append before returning. The same frame that chooses a node must also unchoose it.
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
You will see how one shared path buffer, appended on entry and popped on exit, records every root-to-leaf path.
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
Forgetting
path.pop(): one branch's nodes leak into the sibling's paths.Recording when only one child is missing: half-finished paths such as
"1"in[1,2]get recorded.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.
So: append the node, record a joined snapshot at a true leaf, explore both children, pop.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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 .
Forgetting path.pop() leaks one branch's nodes into its sibling's paths ([1,2,3] wrongly yields "1->2->3"). 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 need no special handling as long as each value is converted with str() before joining.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| path.append(node.val) | path.append(str(node.val)) | The buffer grows by exactly this node on entry |
| if node.left is None and node.right is None: results.append(list(path)) | if not node.left and not node.right: paths.append("->".join(path)) | Only complete root-to-leaf paths are recorded, as immutable snapshots |
| dfs_record_paths(node.left, path, results); dfs_record_paths(node.right, path, results) | dfs(node.left); dfs(node.right) | Children see the path up to and including this node |
| path.pop() | path.pop() | The buffer is restored before the frame returns |