Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths, each as a string with node values joined by "->". A leaf is a node with no children. Paths are returned in preorder (left before right).

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

DFS from the root, carrying the list of values on the current route.

When you reach a leaf, join the collected values with '->' and record the path.

Recurse left before right to list the paths in preorder.

Common doubts

Only at a leaf — a node with neither a left nor a right child; interior nodes never emit a path.

Append immutably (build a new list/string per call) or push then pop the value when backtracking, so each branch sees only its own ancestors.

Preorder — left branch before right — because we recurse (or pop) left first.

Interview follow-ups

· What an interviewer asks next.

Carry a running number (num*10 + val) down and add it at each leaf, rather than building strings.

Carry the remaining target down and record the path when it hits zero at a leaf.

Fun facts

This 'carry state down, snapshot at leaves' pattern powers path-sum, sum-of-numbers, and many backtracking problems.
The number of root-to-leaf paths equals the number of leaves in the tree.

Asked at

AmazonGoogleApple

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3, null, 5]
Output: ["1->2->5", "1->3"]
Two root-to-leaf paths: 1->2->5 and 1->3.

Example 2

Input: root = [1]
Output: ["1"]
A single node is itself a root-to-leaf path.

Constraints

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

Every root-to-leaf path is exactly the sequence of nodes on one downward route. Carry the path down as you recurse; when you hit a leaf, snapshot the accumulated values joined by \"->\". Recursing left before right yields the paths in preorder.

Prerequisites

Before you start

· Concepts used directly in the solution.

DFS carrying state. Pass the current path down the recursion.

Leaf detection. A node with no left and no right child ends a path.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Output

“What format for each path?”

Node values joined by '->', e.g. '1->2->5'.

“What counts as a leaf?”

A node with neither a left nor a right child.

The ideal opening — say it like this

I DFS from the root, carrying the path of values so far.

At each leaf I join the path with '->' and add it to the answer; recursing left before right gives preorder.

Understand the problem

Worked example — tree [1, 2, 3, null, 5]

        1
       / \
      2   3
       \
        5
paths: 1->2->5  (left branch to leaf 5)
       1->3     (right branch to leaf 3)
result: ["1->2->5", "1->3"]

Key observations

1Aha

Carry the path down

The state you thread through the recursion is the list of ancestor values; a leaf turns it into an output string.

2Aha

Snapshot only at leaves

Interior nodes never emit a path; only nodes with no children do.

3Aha

Left-before-right gives preorder

Recursing (or popping) the left branch first lists the paths top-to-bottom, left-to-right.

Brute force vs optimal

	Iterative (explicit stack)	Recursive DFS
Idea	Stack of (node, path-string), push right then left	Carry the path, emit at leaves
Time	O(n * L)	O(n * L)
Space	O(n * L)	O(height * L)

Both are O(n·L) where L is the path length; the recursion is the clearest. Full code is in the Approaches selector below.

Summary

Key takeaway

DFS carrying the path of node values; at each leaf, join with '->' and record. Recurse left before right for preorder. O(n·L) time.

dfs(node, path):
    path = path + [node.val]
    if node is a leaf: emit join(path, "->"); return
    dfs(node.left, path); dfs(node.right, path)