Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5] Output: [“1->2->5”,“1->3”]

Example 2:

Input: root = [1] Output: [“1”]

Constraints:

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

Approach: DFS with Backtracking

Algorithm

1. Traverse the tree with DFS, accumulating the current path
2. When a leaf node (no left or right child) is reached, add the path to the result
3. Recurse into left and right children, appending "->" before each child value

Time & Space Complexity

• Time Complexity: O(N) - every node is visited once; the string building costs O(H) per leaf
• Space Complexity: O(H) - the recursion stack depth, plus O(N) for the result

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * Return all root-to-leaf paths.
     * @param root Root of the binary tree
     * @return List of paths in "1->2->5" format
     */
    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;
        }

        String current = path.isEmpty() ? String.valueOf(node.val)
                                        : path + "->" + node.val;

        if (node.left == null && node.right == null) {
            result.add(current);
            return;
        }

        dfs(node.left, current, result);
        dfs(node.right, current, result);
    }

    // Test method
    public static void main(String[] args) {
        BinaryTreePaths btp = new BinaryTreePaths();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);

        System.out.println("Input: root = [1,2,3,null,5]");
        System.out.println("Output: " + btp.binaryTreePaths(root));
        // Expected: ["1->2->5","1->3"]
    }
}

Example Walkthrough

For root = [1,2,3,null,5]:

1. At node 1, path = “1”
2. Go left to node 2, path = “1->2”; recurse into its right child 5, path = “1->2->5”, leaf -> record
3. Back at node 1, go right to node 3, path = “1->3”, leaf -> record

Result: ["1->2->5","1->3"].

Key Points

1. Leaf Termination: A path ends only at nodes without children
2. String Accumulation: Passing the built string avoids a separate backtracking structure
3. Immutability: Each recursion builds a new string, so no undo step is needed
4. Empty Root: A null root simply produces an empty result
5. DFS Order: Any order is acceptable per the problem statement