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]

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.

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