Problem statement

Given the root of a binary tree, return every path from the root to a leaf (a node with no children). Write each path as its node values joined by "->", for example "1->2->5".

List the paths in the left-to-right order of their leaves — the order a depth-first walk that visits left children before right children reaches them.

Example 1

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
Explanation: The leaves are 5 (under 2) and 3; 5 is further left, so its path comes first.

Example 2

Input: root = [1]
Output: ["1"]

Example 3

Input: root = [-3,null,4,8,-2]
Output: ["-3->4->8","-3->4->-2"]
Explanation: Negative values keep their minus sign inside the path text.

Constraints

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

Hints for Binary Tree Paths

1. Hint 1

   A root-to-leaf path is exactly what a depth-first walk holds on its call stack when it reaches a leaf.

2. Hint 2

   Carry the current path down — as a list of values or as the string built so far — and record it at each leaf.

3. Hint 3

   Visiting the left child before the right one produces the leaves, and so the paths, in the required left-to-right order.

How to solve Binary Tree Paths

Depth-first search from the root, keeping the values on the way down. Each time the walk stands on a leaf, the values it holds form one complete path; visiting left before right emits the paths in left-to-right leaf order.

Approach

1. Start a DFS at the root with an empty path.
2. On entering a node, append its value to the path.
3. If the node is a leaf, join the path with "->" and add it to the answer.
4. Recurse into the left child, then the right child, then remove the node's value again (backtrack).

Why it works

Each leaf is reached exactly once, and at that moment the path holds precisely the nodes from the root to it — every node appended on the way down has not yet been popped, and every finished branch has been. A preorder walk with left before right reaches leaves from left to right.

Complexity

• Time — O(n · h) — each of up to n/2 leaves copies a path of length up to h
• Space — O(h) for the recursion and the current path, plus the output

Pitfalls

• Only leaves end a path; a node with one child must not emit one.
• Forgetting to pop the value after the recursive calls leaks one branch's nodes into the next path.
• A single-node tree has the one path "<value>" with no arrow.

Reference solution

Python

from typing import List, Optional

def binaryTreePaths(root: Optional[TreeNode]) -> List[str]:
    out = []
    path = []

    def walk(node):
        path.append(str(node.val))
        if node.left is None and node.right is None:
            out.append("->".join(path))
        if node.left is not None:
            walk(node.left)
        if node.right is not None:
            walk(node.right)
        path.pop()

    if root is not None:
        walk(root)
    return out

Java

public static String[] binaryTreePaths(TreeNode root) {
    List<String> out = new ArrayList<>();
    if (root != null) pathWalk(root, new ArrayList<Integer>(), out);
    return out.toArray(new String[0]);
}

static void pathWalk(TreeNode node, List<Integer> path, List<String> out) {
    path.add(node.val);
    if (node.left == null && node.right == null) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) sb.append("->");
            sb.append(path.get(i));
        }
        out.add(sb.toString());
    }
    if (node.left != null) pathWalk(node.left, path, out);
    if (node.right != null) pathWalk(node.right, path, out);
    path.remove(path.size() - 1);
}

C++

void pathWalk(TreeNode* node, vector<int>& path, vector<string>& out) {
    path.push_back(node->val);
    if (!node->left && !node->right) {
        string s;
        for (size_t i = 0; i < path.size(); i++) {
            if (i > 0) s += "->";
            s += to_string(path[i]);
        }
        out.push_back(s);
    }
    if (node->left) pathWalk(node->left, path, out);
    if (node->right) pathWalk(node->right, path, out);
    path.pop_back();
}

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> out;
    vector<int> path;
    if (root) pathWalk(root, path, out);
    return out;
}

JavaScript

var binaryTreePaths = function(root) {
    var out = [];
    if (root !== null) pathWalk(root, [], out);
    return out;
};

var pathWalk = function(node, path, out) {
    path.push(node.val);
    if (node.left === null && node.right === null) out.push(path.join("->"));
    if (node.left !== null) pathWalk(node.left, path, out);
    if (node.right !== null) pathWalk(node.right, path, out);
    path.pop();
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy