Programming Practice: Find paths that sum to a given value

findPaths.cpp

// find all paths in a binary tree
// which sum to a given value

#include <iostream>
#include <vector>

struct Node {
    int val;
    Node * left, *right;
    Node(int v) : val(v) {
        left = NULL;
        right = NULL;
    }
};

void printPaths(Node * root, int sum, std::vector<Node *> history) {
    if(root == NULL) 
        return;
    size_t level = history.size();
    history.push_back(root);
    int hist_sum = 0;
    for(int i = level; i >= 0; --i) {
        hist_sum += history[i]->val;
        if (hist_sum == sum) {
            for(int j = i; j <= level; ++j) 
                std::cout << history[j]->val << " ";
            std::cout << std::endl;
            break;
        }
    }
    printPaths(root->left, sum, history);
    printPaths(root->right, sum, history);
    return;
}

int main() {

    // an example tree
    //        1
    //      /   \
    //     2     3
    //    / \   / \
    //   4   5 6   7
    //
    Node * root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(4);
    root->right->right = new Node(7);
    std::vector<Node*> history;

    // find paths that sum to 7
    printPaths(root, 7, history);

    return 0;
}