Log inSign up
easyleetcodeNot Started

Binary Tree Paths

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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

A leaf is a node with no children. Each path must be represented as a string formatted with arrows (e.g., "1->2->5").

Example 1 · Example 1: Tree with Multiple Leaves:

Input: root = [1, 2, 3, null, 5] Tree: 1 / \ 2 3 \ 5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5 and 1->3.

Example 2 · Example 2: Single Node:

Input: root = [1] Tree: 1
Output: ["1"]
Explanation: Root is itself the only leaf.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master root-to-leaf path identification.
  • Understand string path building vs backtracking array approach.
  • Formulate robust leaf termination checks.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • All root-to-leaf paths.
  • String representation with ->.
  • Leaf-terminated collection.

Algorithmic Decision Tree:

  • If node.left == null && node.right == null -> append currentPath to result.
  • If node.left != null -> dfs(node.left, path + -> + node.left.val).
  • If node.right != null -> dfs(node.right, path + -> + node.right.val).

Connected Patterns:

Path Sum IISmallest String Starting From LeafSum Root to Leaf Numbers

1. BFS with Queue Storing Node & Path

Intuition

Push root and to_string(root->val) into a queue. For each popped node, if it is a leaf, push its path string to the answer. Otherwise, append children and updated paths to queue.

When to apply: When avoiding recursion is required.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue stores pairs (node, pathString). Push (root, String(root.val)).
  3. Step 3: Pop (curr, path). If curr has no children, add path to result.
  4. Step 4: If curr.left != null, enqueue (curr.left, path + -> + curr.left.val).
  5. Step 5: If curr.right != null, enqueue (curr.right, path + -> + curr.right.val).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<string> binaryTreePaths(TreeNode* root) {
10 if (!root) return {};
11 vector<string> res;
12 queue<pair<TreeNode*, string>> q;
13 q.push({root, to_string(root->val)});
14 while (!q.empty()) {
15 auto [node, path] = q.front(); q.pop();
16 if (!node->left && !node->right) {
17 res.push_back(path);
18 }
19 if (node->left) q.push({node->left, path + "->" + to_string(node->left->val)});
20 if (node->right) q.push({node->right, path + "->" + to_string(node->right->val)});
21 }
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n * h) — Copying strings of length up to h for each node.
  • Space complexity: O(n * h) — Queue holds pairs of nodes and string paths.

2. Recursive DFS with String Concatenation

Intuition

Call dfs(node, path). If node is a leaf, add path to result. Otherwise, recurse to left and right with path + -> + child.val.

When to apply: Concise recursive solution.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Define dfs(node, path, res).
  3. Step 3: If node.left == null && node.right == null, res.push(path).
  4. Step 4: If node.left != null, dfs(node.left, path + -> + node.left.val, res).
  5. Step 5: If node.right != null, dfs(node.right, path + -> + node.right.val, res).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, string path, vector<string>& res) {
10 if (!node->left && !node->right) {
11 res.push_back(path);
12 return;
13 }
14 if (node->left) dfs(node->left, path + "->" + to_string(node->left->val), res);
15 if (node->right) dfs(node->right, path + "->" + to_string(node->right->val), res);
16 }
17 vector<string> binaryTreePaths(TreeNode* root) {
18 if (!root) return {};
19 vector<string> res;
20 dfs(root, to_string(root->val), res);
21 return res;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n * h) — String copying takes O(h) at each of the leaf paths.
  • Space complexity: O(h) — Recursion call stack takes O(h).

3. Backtracking with Dynamic Node List

Intuition

Push node.val to a shared vector/list. When a leaf is reached, join the vector with -> and store. Pop node.val upon returning from recursion (backtrack). This eliminates all intermediary string copies.

When to apply: Optimal memory solution: avoids intermediate string allocations during recursion.

Algorithm

  1. Step 1: Maintain a shared array currentPath.
  2. Step 2: Add node.val to currentPath.
  3. Step 3: If leaf (left == null && right == null), format string from currentPath and add to res.
  4. Step 4: Recurse on left and right children.
  5. Step 5: Pop the last element from currentPath before returning.

DFS Path Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root (1)
Visual state
Values and pointers at this exact step
tree
Root
1
L (Leaf)
2
R
3

Node order shown; add connections to display explicit tree edges.

path 1: 2
Check / comparison
Node 2 is leaf -> Save '1->2'
Decision / next transition
Add '1->2' to result paths.
Why this step matters

Step 1: Start at root (1). Traverse left to child 2. Node 2 has no children (leaf). Record path: 1->2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void backtrack(TreeNode* node, vector<int>& path, vector<string>& res) {
10 path.push_back(node->val);
11 if (!node->left && !node->right) {
12 string s = to_string(path[0]);
13 for (int i = 1; i < path.size(); ++i) s += "->" + to_string(path[i]);
14 res.push_back(s);
15 } else {
16 if (node->left) backtrack(node->left, path, res);
17 if (node->right) backtrack(node->right, path, res);
18 }
19 path.pop_back();
20 }
21 vector<string> binaryTreePaths(TreeNode* root) {
22 if (!root) return {};
23 vector<string> res;
24 vector<int> path;
25 backtrack(root, path, res);
26 return res;
27 }
28};
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n) — Each node added and removed from path once. String created only at leaf nodes.
  • Space complexity: O(h) — Path array and recursion stack both take at most O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS with Queue PathsO(n * h)O(n * h)Queue holds pairs of node and string path.String duplication at each queue state.
2.DFS with String ConcatenationO(n * h)O(h)Pass updated path string on recursive calls.String copying.
3.Backtracking with Dynamic Node ListOptimalO(n)O(h)Mutable list with push and pop; construct string only at leaf nodes.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root = [1] -> returns [1].
  • Skewed tree: returns a single path string with all nodes.
  • Negative node values: handled correctly (e.g. -1->-2).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Discuss the trade-off between immutable string concatenation (creates temporary strings) vs mutable vector/list backtracking (pop_back after recursion).
  2. Ensure you verify that leaf check requires BOTH children to be null.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is a mutable array with push and pop (backtracking) more memory efficient than string concatenation?

Back to DSA Sheet