Comment on page
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
Last modified 4yr ago