CareerCup

bool ContainsSum(btree *root, int N)
{
if(!root)
return(N == 0)
else{
int remsum = N - root->value;
return((ContainsSum(node->left, remsum)) || (ContainsSum(node->right, remsum)));
}
}

a small change in the above code pls replace node by root

How does this code return the actual path from the root node to the leaf ? I think it just returns whether such a path exists or not.

Even that it doesnt as there is a possibility of sum getting equal to the given value at an interior node whereas the question specifically says for leaf

/// <summary>
        /// Prints the paths to next smallest node.
        /// </summary>
        /// <param name="root">The root.</param>
        /// <param name="nodeValueToSearch">The node value to search.</param>
        public void printSumOfPathsToANode(BinaryTreeNode root, int nodeValueToSearch)
        {
            var path = new int[1000];
            printSumOfPathsToANode(root, path, 0, nodeValueToSearch);
        }

        /// <summary>
        /// Recursive printPaths helper -- given a node, and an array containing
        /// the path from the root node up to but not including this node,
        /// prints out all the root-leaf paths.
        /// </summary>
        /// <param name="node">The node.</param>
        /// <param name="path">The path.</param>
        /// <param name="pathLen">The path len.</param>
        /// <param name="nodeValueToSearch">The node value to search.</param>
        private static void printSumOfPathsToANode(BinaryTreeNode node, int[] path, int pathLen, int nodeValueToSearch)
        {
            if (node == null) return;

            nodeValueToSearch -= node.Name;
            // append this node to the path array
            path[pathLen] = node.Name;
            pathLen++;


            // it's a leaf, so print the path that led to here
            if (nodeValueToSearch == 0)
            {
                printArraySumOfPathsToANode(path, pathLen);
            }
            else
            {
                // otherwise try both subtrees
                printSumOfPathsToANode(node.Left, path, pathLen, nodeValueToSearch);
                printSumOfPathsToANode(node.Right, path, pathLen, nodeValueToSearch);
            }
        }

        /**
         Utility that prints ints from an array on one line.
        */
        private static void printArraySumOfPathsToANode(int[] ints, int len)
        {
            Console.WriteLine("New Path Started");

            int i;
            for (i = 0; i < len; i++)
            {
                Console.WriteLine(ints[i] + " ");
            }
            Console.WriteLine("Path Ended");
        }

I think DFS can be used.

use the logic as given for the first response and tweak it a bit for adding the path for each traversal of nodes and you're done!

this is the working code for a binary tree, can be easily expanded to use for n-ary tree:
<code snippet in CPP>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
}Node;

void makeBTree(string givenString)throw() {
    cout << "given input= " << givenString << endl;
    stack<Node *> nodeStack;
    Node *temp;
    int ix=0;

    while(givenString[ix] !='\0') {
        if (isdigit(givenString[ix])) {
            temp = new Node;
            temp->data = givenString[ix] - '0';
            temp->left = NULL;
            temp->right = NULL;
            nodeStack.push(temp);
        }
        if (givenString[ix]==')' && nodeStack.size()>1) {
            temp = nodeStack.pop();
            Node *last = nodeStack.pop();
            if (last->left == NULL) {
                last->left = temp;
            } else if (last->right == NULL) {
                last->right = temp;
            }
            nodeStack.push(last);
        }

        ix++;
    }
}

test run:
i/p: (1(2(3)(4))(5(6)))
o/p: 3 2 4 1 6 5 //inorder traversal, to test the validity

// returns true if the tree has a path with the specified sum
static int
hasPathSum(node_t *subtree, int sum)
{
	if (subtree && (((subtree->left == subtree->right) && subtree->key == sum) || 
		(hasPathSum(subtree->left, sum - subtree->key) || hasPathSum(subtree->right, sum - subtree->key)))) {
		cout << subtree->key << ", ";
		return 1;
	}

	return 0;
}

call --> findPathOfLen_N(root, 0, N)

findPathOfLen_N(node* curr, K, N)
{

if(currr == NULL){
cout << "No such path exists";
return false;
}

if(curr->data + K == N)
if(curr->left == NULL && curr->right == NULL)
{
print(curr->data);
return true;
}

if(curr->data->left != NULL)
if (function(curr->left, K-curr->data, N))
return true;
if(curr->data->right != NULL)
if (function(curr->right, K-curr->data, N))
return true;

return false;
}

bool ContainsSum(btree *node, int N)
{
if(node==NULL)
return(N == 0)
return((ContainsSum(node->left, N-node->data)) || (ContainsSum(node->right, N-node->data)));
}

bool ContainsSum(btree *node, int N)
{
if(node==NULL) return(N == 0);
return((ContainsSum(node->left, N-node->data)) || (ContainsSum(node->right, N-node->data)));
}

olution can be found on stanfords website
hxxp://cslibrary.stanford.edu/110/BinaryTrees.pdf (similar to Rockey solution)