// Given a binary tree, return all paths from the root to leaves.
// For example, given the tree
// 1
// / \
// 2 3
// / \
// 4 5
// it should return[[1, 2], [1, 3, 4], [1, 3, 5]].
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <sstream>
#include <thread>
#include <map>
#include <vector>
#include <string>
using namespace std;
class Node
{
public:
int value;
Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
Node(int newValue, Node* nodeParent = nullptr)
{
value = newValue;
parent = nodeParent;
}
};
void printPath(vector<int> path)
{
for (unsigned i = 0; i < path.size(); ++i)
{
cout << path[i] << ", ";
}
cout << endl << "---------------" << endl;
}
void getPathsRecur(struct Node* node, vector<int> path, vector<vector<int>> &pathList)
{
if (node == nullptr)
return;
// add the current value to the path
path.push_back(node->value);
// push the path if we encounter a leaf node
if (node->left == nullptr && node->right == nullptr)
{
// add the path to pathList
pathList.push_back(path);
//printPath(path);
}
else
{
// else: try both subtrees
getPathsRecur(node->left, path, pathList);
getPathsRecur(node->right, path, pathList);
}
}
vector<vector<int>> getPaths(Node* rootNode)
{
Node* node = rootNode;
vector<int> currentPath = vector<int>();
vector<vector<int>> pathList = vector<vector<int>>();
getPathsRecur(node, currentPath, pathList);
return pathList;
}
Node* makeTree()
{
Node* head = new Node(1);
head->left = new Node(2, head);
head->right = new Node(3, head);
head->right->left = new Node(4, head->right);
head->right->right = new Node(5, head->right);
cout << "Tree constructed" << endl;
return head;
}
int main(int argc, char** argv)
{
auto tree = makeTree();
auto result = getPaths(tree);
for(unsigned i = 0; i < result.size(); ++i)
{
printPath(result[i]);
}
cout << "Finished" << endl;
return 0;
}
Comments