Binary Tree Paths

Binary Tree Paths is a depth-first search problem. The goal is to collect every root-to-leaf path in a binary tree and format each path as a string.

The useful pattern is: carry the path so far, and when the current node is a leaf, save the completed path.

Problem

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

A root-to-leaf path starts at the root and ends at a leaf node. A leaf is a node with no left child and no right child.

Example:

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

result = ["1->2->5", "1->3"]

First Attempt

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();

    if (root == null) return paths;

    if (root.left == null && root.right == null) {
        paths.add("" + root.val);
        return paths;
    }

    binaryTreePaths(root.left, paths, root.val + "");
    binaryTreePaths(root.right, paths, root.val + "");

    return paths;
}

public void binaryTreePaths(TreeNode root, List<String> paths, String path) {
    if (root == null) return;

    if (root.left == null && root.right == null) {
        paths.add(path + "->" + root.val);
    }

    binaryTreePaths(root.left, paths, path + "->" + root.val);
    binaryTreePaths(root.right, paths, path + "->" + root.val);
}

The recursion idea is right:

• start with the root value
• pass the current path into each child
• add the path when a leaf is reached

There is one small inefficiency: after adding a leaf path, the helper still calls both children. Those calls immediately return because both children are null, so the result is still correct. We can return as soon as the leaf is handled.

Clean Version

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

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();

        if (root == null) {
            return paths;
        }

        collectPaths(root, "", paths);
        return paths;
    }

    private void collectPaths(TreeNode node, String path, List<String> paths) {
        if (node == null) {
            return;
        }

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

        if (node.left == null && node.right == null) {
            paths.add(currentPath);
            return;
        }

        collectPaths(node.left, currentPath, paths);
        collectPaths(node.right, currentPath, paths);
    }
}

LeetCode provides the TreeNode class:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

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

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Walkthrough

Input:

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

Tree shape:

    1
   / \
  2   3
   \
    5

Steps:

Final result:

["1->2->5", "1->3"]

Why DFS Fits

Each recursive call knows two things:

• the current node
• the path used to reach that node

When the node is not a leaf, the same question is passed down to its children.

When the node is a leaf, the path is complete. There is nothing else to explore below it.

Edge Cases

root = [] -> []
root = [1] -> ["1"]
root = [1,2] -> ["1->2"]
root = [1,null,3] -> ["1->3"]

The single-node tree matters because the root is also a leaf.

Complexity

n is the number of nodes and h is the height of the tree.

The traversal visits every node once. The path strings can be up to height h, and the output may contain many root-to-leaf paths, so the string-building and result storage cost matters.

The recursion stack alone is O(h).

Takeaways

• Use DFS when a path must be carried from root to leaf.
• A leaf is node.left == null && node.right == null.
• Add the path at the leaf, then return.
• For a single-node tree, the answer is just the root value as a string.