Why is the current node removed during backtracking?

The same currentPath is reused across different branches. Removing the node restores the path to its parent's state before another subtree is explored.

Why is a copy of currentPath stored when a leaf is reached?

currentPath continues changing as backtracking proceeds. Saving the same list reference would cause previously recorded paths to change, so a copy must be stored.

What happens if the tree contains only one node?

The root is also a leaf, so the only root-to-leaf path contains that single value. For example, a tree containing only node 5 returns [[5]].

What is the main improvement of backtracking over passing separate path copies?

Backtracking maintains only one active path and reuses it across branches. This avoids repeatedly copying partial paths during traversal and reduces auxiliary space to O(H).

Print root to leaf path in Binary Tree

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

A root-to-leaf path starts at the root and ends at a leaf node. A leaf is a node that has no left or right child.

Each path should contain the node values in the same order in which they appear from the root to the leaf.

Example 1

Input:
root = [1, 2, 3, null, 5]

Output:
[[1, 2, 5], [1, 3]]

Explanation:
There are two root-to-leaf paths: 1 -> 2 -> 5 and 1 -> 3.

Example 2

Input:
root = [1, 2, 3, 4, 5, null, 6]

Output:
[[1, 2, 4], [1, 2, 5], [1, 3, 6]]

Explanation:
The leaf nodes are 4, 5, and 6, so the corresponding root-to-leaf paths are 1 -> 2 -> 4, 1 -> 2 -> 5, and 1 -> 3 -> 6

Approach 1

To construct a root-to-leaf path, every node needs access to the sequence of nodes visited before reaching it.

Two variables are used:

currentPath stores the sequence of node values from the root to the current node.
paths stores all completed root-to-leaf paths found during traversal.

A straightforward DFS approach is used in which each recursive branch receives its own copy of currentPath. Because each branch owns a separate path copy, changes made while exploring one subtree cannot affect another subtree.

Whenever a leaf node is reached, the current path already represents a complete root-to-leaf path and is stored in paths.

This avoids the need to undo changes while returning from recursion, but repeatedly copying partial paths creates additional work and memory usage.

Algorithm

If root is null, an empty paths list is returned because no root-to-leaf path exists.
A result list paths is maintained to store completed paths, while currentPath is used to represent the path from the root to the currently visited node.
Whenever a node is visited, its value is appended to currentPath because it becomes part of the active root-to-node path.
If the current node is a leaf, the completed currentPath is stored in paths.
Before the left and right children are explored, separate copies of currentPath are passed to those recursive calls so that modifications in one branch cannot affect the other.
After every reachable leaf has been processed, all paths stored in paths are returned.

Dry Run

Root to Leaf Paths Appraoch 1 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Builds root-to-leaf paths using
  // a separate path for each branch.
  void dfs(
      TreeNode* node,
      vector<int> currentPath,
      vector<vector<int>>& paths
  ) {
      // An empty subtree cannot
      // extend the current path.
      if (node == nullptr) {
          return;
      }
30
      currentPath.push_back(node->val);
32
      // A leaf completes one
      // valid root-to-leaf path.
      if (
          node->left == nullptr
          && node->right == nullptr
      ) {
          paths.push_back(currentPath);
          return;
      }
42
      // Each recursive call receives
      // its own copy of currentPath.
      dfs(
          node->left,
          currentPath,
          paths
      );
50
      dfs(
          node->right,
          currentPath,
          paths
      );
  }
57
58public:
  // Returns all paths starting at
  // the root and ending at leaves.
  vector<vector<int>> rootToLeafPaths(
      TreeNode* root
  ) {
      vector<vector<int>> paths;
65
      if (root == nullptr) {
          return paths;
      }
69
      vector<int> currentPath;
71
      dfs(
          root,
          currentPath,
          paths
      );
77
      return paths;
  }
80};
81
82int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->right = new TreeNode(5);
87
  Solution solution;
89
  vector<vector<int>> paths =
      solution.rootToLeafPaths(root);
92
  for (auto& path : paths) {
      cout << "[ ";
95
      for (int value : path) {
          cout << value << " ";
      }
99
      cout << "]" << endl;
  }
102
  return 0;
104}

Complexity Analysis

Let N be the number of nodes in the binary tree, H be the height of the tree, and K be the total number of node values contained across all returned root-to-leaf paths.

Time Complexity: O(N × H + K) in the worst case. A path copy may contain up to O(H) values for each visited node, while storing all completed paths requires a total of O(K) work.

Space Complexity: O(H²) auxiliary space in the worst case, excluding the returned paths. Multiple copied paths of length up to H may coexist across recursive calls.

Approach 2

The repeated copying performed in Approach 1 is unnecessary because DFS explores only one root-to-current-node route at a time.

Instead, a single mutable list currentPath is maintained. It always represents the active path from the root to the current node, while paths stores copies of completed root-to-leaf paths.

When a node is entered, its value is added to currentPath. If a leaf is reached, a copy of currentPath is stored in paths.

After both child subtrees have been explored, the current node is removed from currentPath. This restores the path to the exact state it had before that node was entered.

This follows the backtracking pattern:

Choose → Explore → Undo

Algorithm

A result list paths and a mutable list currentPath are maintained, where paths stores completed root-to-leaf paths and currentPath represents the active root-to-node route.
If the current node is null, the recursive call is terminated because no path can be extended through an empty subtree.
When a non-null node is entered, its value is appended to currentPath because it becomes part of the active path.
If the current node is a leaf, a copy of currentPath is stored in paths because a complete root-to-leaf path has been formed.
Otherwise, the left and right children are explored recursively using the same currentPath.
After the current node and its descendants have been processed, the current node is removed from currentPath so that the parent path state is restored before another branch is explored.
After DFS has finished, all paths stored in paths are returned.

Dry Run

Root to Leaf Paths Appraoch 2 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Builds paths using one shared
  // path with backtracking.
  void dfs(
      TreeNode* node,
      vector<int>& currentPath,
      vector<vector<int>>& paths
  ) {
      // An empty subtree cannot
      // extend the current path.
      if (node == nullptr) {
          return;
      }
30
      currentPath.push_back(node->val);
32
      // A copy is stored because
      // currentPath changes during backtracking.
      if (
          node->left == nullptr
          && node->right == nullptr
      ) {
          paths.push_back(currentPath);
      } else {
          dfs(
              node->left,
              currentPath,
              paths
          );
46
          dfs(
              node->right,
              currentPath,
              paths
          );
      }
53
      // Remove the current node to
      // restore the parent's path.
      currentPath.pop_back();
  }
58
59public:
  // Returns all paths starting at
  // the root and ending at leaves.
  vector<vector<int>> rootToLeafPaths(
      TreeNode* root
  ) {
      vector<vector<int>> paths;
      vector<int> currentPath;
67
      dfs(
          root,
          currentPath,
          paths
      );
73
      return paths;
  }
76};
77
78int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->right = new TreeNode(5);
83
  Solution solution;
85
  vector<vector<int>> paths =
      solution.rootToLeafPaths(root);
88
  for (auto& path : paths) {
      cout << "[ ";
91
      for (int value : path) {
          cout << value << " ";
      }
95
      cout << "]" << endl;
  }
98
  return 0;
100}

Complexity Analysis

Let N be the number of nodes in the binary tree, H be the height of the tree, and K be the total number of node values contained across all returned root-to-leaf paths.

Time Complexity: O(N + K). Every tree node is visited once, while copying each completed path into paths contributes a total of O(K) work.

Space Complexity: O(H) auxiliary space, excluding the returned paths. The recursion stack and currentPath each contain at most one root-to-leaf route at a time.

Interview follow-up Questions

A valid path must start at the root and end at a leaf. Storing paths at internal nodes would create incomplete root-to-node paths.

Print root to leaf path in Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Print root to leaf path in Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why is a path stored only when a leaf node is reached?

Why is the current node removed during backtracking?

Why is a copy of currentPath stored when a leaf is reached?

What happens if the tree contains only one node?

What is the main improvement of backtracking over passing separate path copies?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree