LeetCode: 257. Binary Tree Paths

The problem

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

A leaf is a node with no children.

Example

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

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ans;

    if(root == nullptr) return ans;
    string currentPath;

    vector<string> leftPath, rightPath;
    generatePaths(root, currentPath, ans);

    return ans;
}

void generatePaths(TreeNode* node, string current, vector<string> &arr) {
    if(node == nullptr) return;

    if(current.empty()) current += to_string(node->val);
    else current += "->"+to_string(node->val);

    if(node->left == nullptr && node->right == nullptr) 
    arr.push_back(current);

    TreeNode *left = node->left;
    TreeNode *right = node->right;
    generatePaths(left, current, arr);
    generatePaths(right, current, arr);
}

The generatePaths function is a recursive function that generates paths from a given node down to its leaf nodes. It follows these steps:

1. If the input node is nullptr (represents an empty node), the function stops and returns.
2. If the current path is empty, it adds the value of the current node to the path. Otherwise, it appends "->" and the value to the path.
3. If the current node is a leaf node (has no left or right children), the current path is complete, and it's added to the vector arr which stores all the generated paths.
4. The function then retrieves the left and right children of the current node.
5. It recursively calls itself for both the left and right children while passing the updated path and the vector of paths. This step is crucial because it explores all possible paths in the binary tree, traversing through all the nodes.

In summary, the binaryTreePaths function initializes the path generation process and then delegates the task to the generatePaths recursive function, which systematically constructs the paths and stores them in the final vector.