CareerCup

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef struct tree {
struct tree *left;
struct tree *right;
int item;
}nod;

void create ( nod **root,int num )
{
nod *t, *u;
t = *root;
if ( t == NULL ) {
u = new nod;
u -> right = NULL;
u -> left = NULL;
u ->item = num;
*root = u;
}else if ( t -> item <= num ) {
create ( & ( t -> right ), num );
}else if ( t -> item > num ) {
create ( & ( t -> left ), num );
}
}
bool check_sum ( nod *root, int sum){
if ( root != NULL ){
printf("%d\t%d\n", root ->item, sum);
if ( root ->left == NULL && root ->right == NULL && (sum - root->item == 0)){
printf ( "found\n");
return true;
}
check_sum ( root ->left, sum - root ->item);
check_sum ( root ->right, sum - root -> item);
}
}
void preorder ( nod *root )
{
if ( root != NULL ) {
printf ( "%d->", root -> item );
preorder ( root -> left );
preorder ( root -> right );
}
}

int main()
{
int n, num;
nod *root = NULL;
scanf ( "%d", &n );
for ( int i = 0; i < n; i++ ) {
scanf ( "%d", &num );
create ( &root, num );
}
preorder ( root );
int sum;
printf( "enter sum\n");
scanf( "%d", &sum);
if (check_sum(root, sum)){
printf("sum exist");
}else {
printf("not exist");
}
return 0;
}

If these questions are really from microsoft interviews, I would say the quality of the interview questions increased 5 times from an year back.

Since this is BST we can stop from going to right node when the sum to current node is less than curent node value

//code for min length path with sum s
std::string sum_min_path(tree *root, int sum, std::string path)
{
	//initial root is null
	if(!root)
		return NULL;
	std::string rv_path = "";
	sum= sum - root->val;
	std::ostringstream s;
	s << root->val;
	std::string val_as_string(s.str());
	path+=val_as_string;
	
	if(sum ==0 && root->left == NULL && root->right == NULL)
	{
		rv_path = path;
	}
	else
	{
		std::string l_path= "";
		std::string r_path= "";
		if(root->left)
			l_path = sum_min_path(root->left, sum, path);
		if(root->right && sum > root->path ) // Condition modified due to BST
			r_path = sum_min_path(root->right, sum, path);
		if(l_path.size()>0 && r_path.size()>0 )//both exist
		{
			if(l_path.size() < r_path.size()) 
				rv_path = l_path;
			else
				rv_path = r_path;
		}
		else if(l_path.size()>0)
			rv_path = l_path;
		else
			rv_path = r_path;
	}
return rv_path;
}

Please check my code based on Sugarcane_farmer's work

//github.com/jerry0715/myREHL6_src/blob/master/BST.c 

#include "BST.h"

int BST_create(struct node **root, int v) {
    if (*root == NULL) {
        *root = (struct node *) malloc(sizeof(struct node));
        if (*root == NULL) {
            return 0; 
        }
  
        (*root)->v = v;
        (*root)->left = (*root)->right = NULL;

        return 1;
   }

   if ((*root)->v > v) {
       return BST_create(&((*root)->left), v);
   } else {
       return BST_create(&((*root)->right), v);
   }
}
static void BST_display(struct node *root) {
    if (root == NULL) return;

    BST_display(root->left);
    printf("%d ", root->v);
    BST_display(root->right);
}

int findPathWithSum(struct node *root, int S) {
    if (root == NULL) { return 0;}
    
    int sum  = S;
    sum = S - root->v;
   
    if (sum == 0 && root->left == NULL && root->right == NULL) {
        printf("%d ", root->v);
        return 1;
    }

    int l_ret, r_ret;
    l_ret = findPathWithSum(root->left, sum);
  
    if (root->right != NULL && sum < root->right->v) {
        return 0;
    } else {
        r_ret = findPathWithSum(root->right, sum);
    }

    if (l_ret > 0 && r_ret > 0) {
        if (l_ret > r_ret) {
            printf("%d ", root->v);
            return r_ret + 1;
        } else {
            printf("%d ", root->v);
            return l_ret + 1;
        }
    } else {
        if (l_ret > 0) {
            printf("%d ", root->v);
            return l_ret + 1;
        } 
        if (r_ret > 0) {
            printf("%d ", root->v);
            return r_ret + 1;
        }
        return 0;
    }
}

int main() {
    int test1[] = {7, 5, 11, 3, 6, 2, 1}; // has 3 paths from root 7 sum as 18

    struct node *root = NULL;

    int i;
    for (i = 0; i < 7; i++) {
        assert(BST_create(&root, test1[i]) == 1);   
    }
    BST_display(root);
    printf("\n");
    int level = 0;

    level = findPathWithSum(root, 18);
    printf("\n level = %d\n", level);    
    assert(level == 2);

    level = findPathWithSum(root, 12);
    printf("\n level = %d\n", level);
    assert(level == 0);
    return 0;
}

O(n) algorithm:
1. find the minimal path weight.
2. traverse the tree, and remember path traversed & path weight
2.1. if encounter a leaf - check if path sum match min, if so print path
2.2. otherwise cont. traversing

c++ implementation:

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

int GetMinPathWeight(node* root) {
    if (root) {
        return root->data + min(GetMinPathWeight(root->right) , GetMinPathWeight(root->left));
    } else {
        return 0;
    }
}

void printPath(node* path) {
    node* curr = path;
    while (curr) {
        cout << curr->data << " ; ";
        curr = curr->left;    
    }
    cout << endl;
}
void PrintAllMinPathW(node* root , node* path , int currW , currint minPathW) {
    //append curr->data to path
    int   weight = currW + root->data;
    node* curr = new node;
    curr->data = root->data;
    curr->left = path;
    
    //child node
    if (!root->right && !root->left) {
        if (weight == minPathW) {
            printPath(curr);
        }
        //free the memory
        node* next;
        while (curr) {
            next = curr->left;
            delete(curr);
            curr = next;
        }
    } else {
        if (root->right)
            PrintAllMinPathW(root->right , curr , weight , minPathW);
        if (root->left)
            PrintAllMinPathW(root->left , curr , weight , minPathW);
    }
}

int MinLengthTreePath(node* root) {
    int minPathW = GetMinPathWeight(root);
    if (root) {
        PrintAllMinPaths(root , NULL , 0 , minPathW);
    }
    return minPathW;
}