# Top-down & bottom-up recursive solutions in C++

• There are two recursive ways to solve this problem.

1. Top-down:

Need a helper function with an additional string to save the output of parent nodes.

• For the non-leaf node, the helper function is recursively called if there are non-empty subtrees.
• For the leaf node, the helper function pushes the string of one path into the final result.

Code:

``````vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
if(root) helper(root, ans, "");
return ans;
}

void helper(TreeNode* root, vector<string>& ans, string s){
if(!root->left && !root->right) ans.push_back(s + to_string(root->val));    // leaf
if(root->left) helper(root->left, ans, s +  to_string(root->val) + "->");   // left subtree
if(root->right) helper(root->right, ans, s + to_string(root->val) + "->");  // right subtree
}
``````

Time complexity: O(N)

2. Bottom-up:

No need to use a helper function and additional strings. However, the time complexity is higher.

• For the leaf node, return the vector with root->val.
• For the non-leaf node, return the vector with (root->val + all possible strings in its subtrees).

Code:

``````vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
if(root){
if(!root->left && !root->right)     // leaf
ans.push_back(to_string(root->val));
if(root->left){                     // left subtree
vector<string> Lchild = binaryTreePaths(root->left);
for(int i=0; i<Lchild.size(); i++){
Lchild[i] = to_string(root->val) + "->" + Lchild[i];
ans.push_back(Lchild[i]);
}
}
if(root->right){                    // right subtree
vector<string> Rchild = binaryTreePaths(root->right);
for(int i=0; i<Rchild.size(); i++){
Rchild[i] = to_string(root->val) + "->" + Rchild[i];
ans.push_back(Rchild[i]);
}
}
}
return ans;
}
``````

Time Complexity: O(N*logN)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.