DFS with Backtracking

We perform a depth-first traversal, building the current path string as we go. When we reach a leaf node (both children are null), we add the complete path to our result list. On the way back (backtracking), we simply do not append further — the string is passed by value so no explicit undo is needed.

Algorithm:

• Start DFS from the root with an empty path string.
• At each node, append the node's value (and "->" if not a leaf) to the current path.
• If the node is a leaf, add the current path to the result list.
• Recurse on the left and right children.

public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); dfs(root, "", result); return result; } private void dfs(TreeNode node, String path, List<String> result) { if (node == null) return; path += node.val; if (node.left == null && node.right == null) { // leaf node — record the complete path result.add(path); return; } path += "->"; dfs(node.left, path, result); dfs(node.right, path, result); }

Trace through Example 1: root = [1,2,3,null,5]

Node visited	Path so far	Action
1	"1->"	recurse left and right
2	"1->2->"	recurse left (null) and right (5)
5 (leaf)	"1->2->5"	add to result
3 (leaf)	"1->3"	add to result

• Time: O(n) — every node is visited exactly once.
• Space: O(n) — recursion stack depth is O(h) where h is the tree height, and the string building is O(n) in the worst case (skewed tree path of length n).