Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be represented as a string with node values separated by "->".

Example 1

Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"] Explanation: Leaf nodes are 5 and 3. The two root-to-leaf paths are 1→2→5 and 1→3.

Example 2

Input: root = [1] Output: ["1"] Explanation: There is only one node which is both root and leaf.

Constraints:

1 <= Number of nodes <= 100
-100 <= Node.val <= 100

Solution: DFS with Backtracking
Complexity Analysis

Solution: 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.

Java

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

Complexity Analysis

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).