Binary Tree Paths

Problem

Return all root-to-leaf paths as strings like "1->2->5".

Constraints

• 1 ≤ nodes ≤ 100

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def binaryTreePaths(self, root):
        res = []
        def dfs(node, path):
            if not node:
                return
            path = path + [str(node.val)]
            if not node.left and not node.right:
                res.append("->".join(path))
            else:
                dfs(node.left, path)
                dfs(node.right, path)
        dfs(root, [])
        return res

Java

import java.util.*;
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> out = new ArrayList<>();
        if (root != null) dfs(out, root, "" + root.val);
        return out;
    }
    private void dfs(List<String> out, TreeNode n, String path) {
        if (n.left == null && n.right == null) { out.add(path); return; }
        if (n.left != null)  dfs(out, n.left,  path + "->" + n.left.val);
        if (n.right != null) dfs(out, n.right, path + "->" + n.right.val);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.