# All Root to Leaf Paths

Given a binary tree, return a 2d dimensional vector that contains all the possible root-to-leaf paths of the tree.

Ex.

```
   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

[5, 1, 3]
[5, 8, 6]
[5, 8, 9]
```

```cpp
template<typename T>
void root_leaf_paths(Node<T> *root, vector<T> &temp, vector<vector<T>> &main) {
    if (root) {
        temp.push_back(root->value);
        if (!root->left && !root->right) {
            main.push_back(temp);
            temp.pop_back();
            return;
        }
        if (root->left) root_leaf_paths(root->left, temp, main);
        if (root->right) root_leaf_paths(root->right, temp, main);
    }
    temp.pop_back();
}

template<typename T>
vector<vector<T>> root_leaf_paths(BST<T> *tree) {
    vector<vector<T>> main;
    vector<T> temp;

    root_leaf_paths(tree->root, temp, main);
    return main;
}

int main()
{
    vector<int> stuff = { 4,2,6,1,5,3,7,9,10,8,23 };
    BST<int> *tree = new BST<int>();

    cout << "INSERTING ... " << endl;
    //srand(time(nullptr));
    for (auto i : stuff) {
        cout << i << " ";
        tree->insert(i);
    }
    cout << endl << endl;
    //pause();

    cout << "OUR TREE ... " << endl;
    tree->prettyPrint_levelOrder();
    cout << endl << endl;
    //pause();

    vector<vector<int>> paths = root_leaf_paths(tree);
    print2d(paths);
}
```

**How it works**

```
   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9
```

* I keep two vectors, one 1d and the other 2d. Both are passed as references because I dont want them to change on the call stack.
* I run a pre-order dfs traversal - each time checking if I've encountered a leaf. If so, I will need to  append the current vector to the 2d main one. I then pop\_back because I know that the next path in the tree will contain the previous vector, with at least the leaf removed. (The paths share a common ancestor).

**Python Version:**

Notice the use of the `deepcopy`. This was necessary because if we were to otherwise pass in the address of `cur`, then future `pop()'s` would internally mess with other paths.

```python
import copy


def _all_root_to_leaf_paths(root, cur, all):
    if root is not None:
        cur.append(root.val)
        if root.left is None and root.right is None:
            all.append(copy.deepcopy(cur))
        _all_root_to_leaf_paths(root.left, cur, all)
        _all_root_to_leaf_paths(root.right, cur, all)
        cur.pop()


def all_root_to_leaf_paths(root):
    cur = []
    all = []
    _all_root_to_leaf_paths(root, cur, all)
    return all
```