Binary Tree Paths

easy tree dfs backtracking string

Problem

Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be formatted as "a->b->c".

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

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

tree (level-order, "null" for empty)

def binary_tree_paths(root):
    result, path = [], []
    def dfs(node):
        if not node: return
        path.append(str(node.val))
        if not node.left and not node.right:
            result.append("->".join(path))
        else:
            dfs(node.left)
            dfs(node.right)
        path.pop()
    dfs(root)
    return result

function binaryTreePaths(root) {
  const result = [], path = [];
  function dfs(node) {
    if (!node) return;
    path.push(String(node.val));
    if (!node.left && !node.right) result.push(path.join("->"));
    else { dfs(node.left); dfs(node.right); }
    path.pop();
  }
  dfs(root);
  return result;
}

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> out = new ArrayList<>();
        dfs(root, new ArrayList<>(), out);
        return out;
    }
    void dfs(TreeNode n, List<String> path, List<String> out) {
        if (n == null) return;
        path.add(String.valueOf(n.val));
        if (n.left == null && n.right == null) out.add(String.join("->", path));
        else { dfs(n.left, path, out); dfs(n.right, path, out); }
        path.remove(path.size() - 1);
    }
}

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> out;
        vector<string> path;
        dfs(root, path, out);
        return out;
    }
    void dfs(TreeNode* n, vector<string>& path, vector<string>& out) {
        if (!n) return;
        path.push_back(to_string(n->val));
        if (!n->left && !n->right) {
            string s;
            for (int i = 0; i < (int)path.size(); i++) { if (i) s += "->"; s += path[i]; }
            out.push_back(s);
        } else { dfs(n->left, path, out); dfs(n->right, path, out); }
        path.pop_back();
    }
};

Explanation

We want every route from the root down to a leaf, written as "a->b->c". The clean way is a depth-first walk that keeps a running path buffer and only records it when it reaches a leaf.

As dfs(node) enters a node, it pushes the node's value onto path. If the node has no children, it is a leaf, so we join the buffer with "->" and add that string to the results. Otherwise we recurse into the left and right children.

The crucial step is the backtrack: right before returning, the node pops itself from path. This undo lets the same buffer be reused for sibling branches without leftover values polluting other paths.

Example: tree [1, 2, 3, null, 5]. We push 1, then 2, then 5 (a leaf) and record "1->2->5". We pop back to 1, push 3 (a leaf) and record "1->3", giving ["1->2->5", "1->3"].

Each node is entered once, and building a path string costs up to its depth, so the total work is roughly O(n·h).

Time: O(n·h) (each path is up to h long) Space: O(h) recursion + output