// Simple node class so we can construct a binary tree to test the function
function node(val)
{
    this.val = val;
    this.left = null;
    this.right = null;
}
 

var findPaths = function(node, v)
{
	var stack1 = [];
	var stack2 = [];
	var p = 0;
	var sum = 0;
	var fullPathSum = 0;
	
	// Helper function that will print out a path that sums to the target value, v
	// This function will print all the values in stack2 starting at index x (yes, it is cheater style to do this with a stack,
	// but such is my love affair with Javascript) ;-)
	function printPath(x)
	{
		x = x || 0;				 // start at 0 if we haven't been given a starting point
		
		var output = '';
		var i, len = stack2.length;	 
		for (i = x; i < len; i++)
		{
			output += stack2[i].val + ',';
		}
		console.log(output);		
	}

	//
	// main logic
	// 
	 
	// start with stack1 populated with the root node
	stack1.push(node);
 
	while (stack1.length > 0)
	{
		// pop stack1 and save the value in stack2 (stack2 will ultimately contain the path(s) we're interested in)
		var n = stack1.pop();
		stack2.push(n);
		
		// the sum so far (does not necessarily include values all the way back to the root)		
		sum += n.val;
		
		// sum so far (including values all the way back to the root)
		fullPathSum += n.val;
		
		// if sum equals the target value, we've found a path, so print it
		if (sum === v)
		{
			printPath(p);
		}
		else
		{
			// if sum has gotten too large (larger than the target) then we need to extract out one or more addends from the front
			// (need to make sure though, that stack2 still has stuff in it -- stack2 represents the path we're testing)
			while (sum > v && p < stack2.length)
			{
				// p is a pointer within the path where we begin summing up the values.
				// if sum is too larger, we need to repeatedly subtract the left-most value
				sum -= stack2[p].val;
				
				// advance the pointer (this essentially removes one value from the left of the path)
				p++;
				
				// check again to see if we might have hit the target value
				if (sum === v)
				{
					printPath(p);
				}
			}
		}
 
 
		// leaf node
		if (!n.left && !n.right)
		{
			var peek;
			
			// cycle back until we find an element with 2 children, or until we can't go any further
			while (true)
			{
				peek = stack2[stack2.length-1];
				if (!peek || peek.right && peek.left)
				{
					break;
				}
				
				// subtract out values as we cycle backwards
				fullPathSum -= stack2.pop().val;
			}

			// update the sum to be the full path sum to this point
			sum = fullPathSum;
			
			// and p also needs to be reset so it matches up with fullPathSum
			p = 0;			
		}
	  
		// push in the node's children (if any) to stack1		
		if (n.left) stack1.push(n.left);
		if (n.right) stack1.push(n.right);
		
		// rinse, repeat!
	}
}
 
var tree = new node(1);
tree.left = new node(5);
tree.left.left = new node(2);
tree.left.left.right = new node(4);
tree.left.left.right.right = new node(10);
tree.left.left.right.right.right = new node(3);
tree.left.left.right.right.right.right = new node(3);
tree.left.left.right.right.right.right.right = new node(1);
tree.left.left.right.right.right.right.right.right = new node(3);
tree.left.left.right.right.right.right.right.right.right = new node(3);
tree.left.left.right.right.right.right.right.right.right.right = new node(1);
tree.left.left.left = new node(10);
tree.left.left.left.right = new node(3);
tree.left.left.left.right.right = new node(4);
tree.left.left.left.left = new node(6);
tree.left.left.left.left.right = new node(1);
tree.left.left.left.left.left = new node(1);
tree.right = new node(9);
tree.right.left = new node(2);
tree.right.left.right = new node(5);
tree.right.right = new node(8);
tree.right.right.right = new node(6);
tree.right.right.right.left = new node(1);
tree.right.right.right.left.right = new node(2);
tree.right.right.right.left.right.left = new node(4);
tree.right.right.right.right = new node(3);
tree.right.right.right.right.right = new node(3);
tree.right.right.right.right.right.left = new node(1);
 
findPaths(tree, 7);