How is Binary Tree Paths different from returning root-to-leaf paths as arrays?

The traversal logic is almost identical. The main difference is the required output format: each root-to-leaf sequence must be converted into a string with "->" placed between consecutive node values.

What happens when the tree contains only the root?

The root is also a leaf, so its value itself forms the only path. For example, a tree containing only node 1 returns ["1"].

How is Binary Tree Paths different from printing root-to-leaf paths as arrays?

The traversal logic is almost the same. The main difference is the required output representation: each root-to-leaf sequence must be converted into a string using "->" between node values.

Binary Tree Paths | takeUforward

Given the root of a binary tree, return all paths that start at the root and end at a leaf node.

Each path should be represented as a string in the form:

node1->node2->node3

where the node values appear in the same order in which they are visited from the root to the leaf.

If the tree is empty, return an empty list.

Example 1

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

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

Explanation:
The tree contains two root-to-leaf paths: 1 -> 2 -> 5 and 1 -> 3. They are returned in the required string format.

Example 2

Input:
root = [1]

Output:
["1"]

Explanation:
The root itself is a leaf, so its value forms the only root-to-leaf path.

Approach 1

Every leaf represents the endpoint of exactly one root-to-leaf path.

A string named currentPath is maintained because it represents the path formed from the root to the currently visited node. A list named paths is maintained to store all completed root-to-leaf path strings.

During DFS, a new path string is created for each recursive branch. When a child is visited, its value is appended to the existing path using "->" as the separator.

Because each recursive call receives its own string, modifications made in one branch do not affect another branch, so explicit backtracking is not required.

When a leaf is reached, currentPath already represents a complete root-to-leaf path and is stored in paths.

The drawback is that partial path strings are repeatedly copied as traversal moves deeper into the tree.

Algorithm

If the tree is empty, an empty paths list is returned because no root-to-leaf path exists.
A string named currentPath is maintained to represent the root-to-current-node path, while paths is maintained to store all completed path strings.
During DFS, the current node's value is appended to currentPath. If the string is initially empty, the node value is added directly so that no leading "->" is introduced.
If the current node is a leaf, currentPath is inserted into paths because a complete root-to-leaf path has been formed.
For each non-null child, a new copy of the path string is passed into the recursive call so that different branches remain independent.
After all reachable leaves have been processed, the path strings stored in paths are returned.

Dry Run

Binary Tree 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 each root-to-leaf path
  // using a separate string for every branch.
  void dfs(
      TreeNode* node,
      string currentPath,
      vector<string>& paths
  ) {
      if (node == nullptr) {
          return;
      }
28
      // The first node is added directly
      // so the path does not start with "->".
      if (currentPath.empty()) {
          currentPath = to_string(node->val);
      } else {
          currentPath += "->" + to_string(node->val);
      }
36
      // A path is complete only when
      // a leaf node is reached.
      if (
          node->left == nullptr &&
          node->right == nullptr
      ) {
          paths.push_back(currentPath);
          return;
      }
46
      // Each recursive call receives its own
      // copy of the partially built path.
      dfs(
          node->left,
          currentPath,
          paths
      );
54
      dfs(
          node->right,
          currentPath,
          paths
      );
  }
61
62public:
  // Returns all root-to-leaf paths
  // in the required string format.
  vector<string> binaryTreePaths(
      TreeNode* root
  ) {
      vector<string> paths;
69
      if (root == nullptr) {
          return paths;
      }
73
      dfs(
          root,
          "",
          paths
      );
79
      return paths;
  }
82};
83
84int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->right = new TreeNode(5);
89
  Solution solution;
91
  vector<string> paths =
      solution.binaryTreePaths(root);
94
  for (const string& path : paths) {
      cout << path << 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 characters contained across all returned path strings.

Time Complexity: O(N × H + K) in the worst case. A newly created path string may contain information from up to H nodes, causing repeated copying while the tree is traversed. Constructing and storing the final path strings requires a total of O(K) additional work.

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

Approach 2

Creating a new path string for every recursive call can be avoided because DFS explores only one root-to-current-node route at a time.

A list named currentPath is maintained because it stores the node values belonging to the currently active recursion path. A list named paths is maintained to store the completed root-to-leaf strings.

When a node is entered, its value is appended to currentPath.

If a leaf is reached, a helper such as buildPath is used to convert the values in currentPath into the required string format.

While constructing the string, "->" is inserted only between consecutive values. It is not appended after the final value, which prevents a trailing arrow.

After the current node's descendants have been processed, its value is removed from currentPath. This backtracking step restores the parent's path so that the same list can safely be reused for another branch.

Algorithm

A list named currentPath is maintained to represent the active root-to-node route, while paths is maintained to store the completed root-to-leaf strings.
If the current node is null, the recursive call is terminated because no path can be extended through an empty subtree.
When a node is visited, its value is appended to currentPath because it becomes part of the active path.
If the current node is a leaf, the values in currentPath are converted into a string using "->" only between consecutive values, and the completed string is inserted into paths.
If the node is not a leaf, its 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's path state is restored for another branch.
After DFS has finished, all path strings stored in paths are returned.

Dry Run

Binary Tree 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:
  // Converts the active node sequence
  // into the required "value->value" format.
  string buildPath(
      const vector<int>& currentPath
  ) {
      string path;
24
      for (
          int i = 0;
          i < currentPath.size();
          i++
      ) {
          // The separator is added only before
          // later values, never before the first.
          if (i > 0) {
              path += "->";
          }
35
          // Adding the separator before later nodes
          // also prevents a trailing "->".
          path += to_string(currentPath[i]);
      }
40
      return path;
  }
43
  // Reuses one currentPath and restores
  // it through backtracking.
  void dfs(
      TreeNode* node,
      vector<int>& currentPath,
      vector<string>& paths
  ) {
      if (node == nullptr) {
          return;
      }
54
      currentPath.push_back(node->val);
56
      // A path is converted to a string only
      // when a complete root-to-leaf route is found.
      if (
          node->left == nullptr &&
          node->right == nullptr
      ) {
          paths.push_back(
              buildPath(currentPath)
          );
      } else {
          dfs(
              node->left,
              currentPath,
              paths
          );
72
          dfs(
              node->right,
              currentPath,
              paths
          );
      }
79
      // The current node is removed so
      // the parent's path is restored.
      currentPath.pop_back();
  }
84
85public:
  // Returns all root-to-leaf paths
  // using one reusable path structure.
  vector<string> binaryTreePaths(
      TreeNode* root
  ) {
      vector<string> paths;
      vector<int> currentPath;
93
      dfs(
          root,
          currentPath,
          paths
      );
99
      return paths;
  }
102};
103
104int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->right = new TreeNode(5);
109
  Solution solution;
111
  vector<string> paths =
      solution.binaryTreePaths(root);
114
  for (const string& path : paths) {
      cout << path << endl;
  }
118
  return 0;
120}

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 characters contained across all returned path strings.

Time Complexity: O(N + K). Every node is visited once, while constructing all completed root-to-leaf strings requires a total of O(K) additional work.

Space Complexity: O(H) auxiliary space, excluding the returned path strings. The recursion stack and currentPath each contain at most one root-to-leaf route at a time. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Interview follow-up Questions

The root is also a leaf, so its value itself forms the only path. For example, root = [1] returns ["1"].

Binary Tree Paths

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