Problem Statement

Given the root of a binary tree. Return all the root-to-leaf paths in the binary tree.

A leaf node of a binary tree is the node which does not have a left and right child.

Examples

Example 1:

Input:
        1
       / \
      2   3
     / \
    4   5
Output: [
         [1, 2, 4],
         [1, 2, 5],
         [1, 3]
        ]

Explanation:
The root-to-leaf paths are:
1 → 2 → 4
1 → 2 → 5
1 → 3

Example 2:

Input:
         1
        / \
       2   3
        \
         5
Output: [
         [1, 2, 5],
         [1, 3]
        ]

Explanation:
The root-to-leaf paths are:
1 → 2 → 5
1 → 3

Example 3:

Input:
        1
         \
          2
           \
            3
Output: [
         [1, 2, 3]
        ]
        
Explanation:
The root-to-leaf path is 1 → 2 → 3. Since there's only one leaf, there is only one path.

Different Approaches

1️⃣ Depth First Search

Intuition:

To find all root-to-leaf paths in a binary tree:

• A root-to-leaf path starts at the root and ends at a leaf node (a node with no children).
• This can be achieved through DFS traversal while maintaining a list of nodes that constitute the current path.
• Upon reaching a leaf node, the current path is stored in the result list.

To implement this:

1. Use recursion to traverse the tree.
2. Pass the current path in each recursive call.
3. When a leaf node is reached, add the current path to the result list.
4. Backtrack after visiting a node to ensure the path is correct for sibling nodes.

Approach:

1. Base Case:
   • If the root is nullptr, there are no paths, so return an empty list.
2. Recursive Case:
   • Add the current node to the path.
   • If the node is a leaf node, store the current path in the result.
   • Otherwise, recursively call the function for the left and right children.
3. Backtracking:
   • After returning from recursion, remove the current node from the path to ensure it doesn't affect other paths.

Code:

#include <iostream>
#include <vector>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void dfs(TreeNode* node, vector<int>& path, vector<vector<int>>& result) {
        if (!node) return;

        // Add current node to the path
        path.push_back(node->val);

        // If it's a leaf node, save the current path
        if (!node->left && !node->right) {
            result.push_back(path);
        } else {
            // Recur for left and right subtrees
            dfs(node->left, path, result);
            dfs(node->right, path, result);
        }

        // Backtrack: remove the current node from the path
        path.pop_back();
    }

    vector<vector<int>> allRootToLeafPaths(TreeNode* root) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(root, path, result);
        return result;
    }
};

// Helper function to build a sample tree
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

// Main function
int main() {
    Solution sol;
    TreeNode* root = buildTree();
    vector<vector<int>> paths = sol.allRootToLeafPaths(root);

    for (const auto& path : paths) {
        for (int val : path) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is visited exactly once during the traversal.
• Space Complexity: O(N) where N is the number of nodes in the binary tree. This is because the stack can potentially hold all nodes in the tree when dealing with a skewed tree (all nodes have only one child), consuming space proportional to the number of nodes.