Binary Tree Paths

EasyTrees · DFS · Backtracking🧩 Tree DFS LeetCode #257 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, list every path that starts at the root and ends at a leaf (a node with no children). Write each path as its node values joined by "->", e.g. "1->2->5". The paths may be returned in any order.

Input[1,2,3,null,5]Output["1->2->5","1->3"]

Input[1]Output["1"]

1 ≤ nodes ≤ 100 · -100 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A root-to-leaf path is exactly the DFS recursion stack at the moment you reach a leaf. Keep one shared buffer for that stack: append on the way down, snapshot it at a leaf, and truncate it on the way back up.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceCombine Child Paths (Divide & Conquer)

Time O(n + L·h²)Space O(L·h)

A leaf's only path is its own value. Any other node asks each child for all of its paths and prefixes val + "->" to every one. Correct by induction, but each of the L leaf paths is rebuilt as a new string at every one of its up to h ancestors.

Java

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    if (root == null) return res;
    if (root.left == null && root.right == null) {
        res.add(String.valueOf(root.val));
        return res;
    }
    for (TreeNode child : new TreeNode[] {root.left, root.right}) {
        for (String tail : binaryTreePaths(child)) {
            res.add(root.val + "->" + tail); // rebuild every path below
        }
    }
    return res;
}

Clean recursion, but repeated string rebuilding costs a factor of h.

BetterTop-Down DFS Passing a String

Time O(n·h)Space O(h²)

Carry the path so far down the recursion as an immutable String. At a leaf, the parameter already is the full path, so add it directly. Each node still copies a string of length O(depth) to extend it, and the call stack holds h such strings.

Java

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    dfs(root, "", res);
    return res;
}
private void dfs(TreeNode node, String path, List<String> res) {
    if (node == null) return;
    String cur = path.isEmpty() ? String.valueOf(node.val) : path + "->" + node.val;
    if (node.left == null && node.right == null) {
        res.add(cur); // full path reached a leaf
        return;
    }
    dfs(node.left, cur, res);
    dfs(node.right, cur, res);
}

Builds each prefix once, but every node still pays for a full string copy.

OptimalDFS with a Backtracking StringBuilder

Time O(n + L·h)Space O(h)

Share one StringBuilder. Remember its length, append the current value, recurse, then setLength back — undoing the append in O(1). Only leaves call toString(), so the work is one append per node plus the size of the output itself.

Java

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    dfs(root, new StringBuilder(), res);
    return res;
}
private void dfs(TreeNode node, StringBuilder sb, List<String> res) {
    if (node == null) return;
    int mark = sb.length();
    if (mark > 0) sb.append("->");
    sb.append(node.val);
    if (node.left == null && node.right == null) {
        res.add(sb.toString()); // copy only at leaves
    } else {
        dfs(node.left, sb, res);
        dfs(node.right, sb, res);
    }
    sb.setLength(mark); // undo this node's append
}

Output-sensitive and allocation-light — the classic backtracking template.

Pro tip

The “save length → append → recurse → restore length” pattern is how every path / combination backtracking problem avoids copies.

At a glance

Level	Approach	Time	Space
Brute Force	Combine Child Paths (Divide & Conquer)	`O(n + L·h²)`	`O(L·h)`
Better	Top-Down DFS Passing a String	`O(n·h)`	`O(h²)`
Optimal	DFS with a Backtracking StringBuilder	`O(n + L·h)`	`O(h)`

Common pitfalls

Adding a path at a null child instead of at a real leaf — one-child nodes yield bogus paths.
Forgetting to restore the builder — later paths inherit stale values.
Appending "->" before the first value → paths like "->1->2".

Interview tips

Define a leaf precisely (both children null) before writing code.
Start with string passing, then mention the StringBuilder backtracking optimisation.
Note the output alone can be O(L·h), so that term is unavoidable.

Pattern

DFS + backtracking path buffer → enumerate or check every root-to-leaf path (sums, strings, numbers).

My notes saved in this browser