You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. Note that a path can start or end anywhere in the tree.

CareerCup4.9

#include <iostream>
#include <vector>

struct Node
{
  int data;
	Node* left;
	Node* right;
	Node(int var)
	{
		data=var;
		left=NULL;
		right=NULL;
	}
};
void Print(int,Node*,std::vector<int>&,int,bool);
int main()
{
	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(6);
	root->right->right = new Node(7);
	std::vector<int> vec;
	Print(0,root,vec,7,true);
}

void Print(int sum,Node* cur, std::vector<int>& vec, int val,bool flag)
{
	using namespace std;
	if(flag==true)
	{
	if(cur->left!=NULL)
	{
		vector<int> vec1;
		Print(0,cur->left,vec1,val,false);
	}
	if(cur->right!=NULL)
	{
		vector<int> vec2;
		Print(0,cur->right,vec2,val,false);
	}
	}
	int total = sum + cur->data;
	if(total == val)
	{
		vec.push_back(cur->data);
		for(vector<int>::iterator iter = vec.begin();iter!=vec.end();iter++)
		{
			cout<<*iter<<" ";
		}
		cout<<endl;
		return;
	}
	else if(total>val)
	{
		return;
	}
	else if(total<val)
	{
		vec.push_back(cur->data);
		vector<int> vecl(vec);
		vector<int> vecr(vec);
		if(cur->left!=NULL)
		{
			Print(total,cur->left,vecl,val,true);
		}
		if(cur->right!=NULL)
		{
			Print(total,cur->right,vecr,val,true);
		}
		return;

	}
}