CareerCup

This can be done using DFS. DFS uses a stack internally. Anytime you reach a leaf node, just print the all nodes in the stack which would be the path from the root to that leaf.

My solution saves the path for each node that is pushed onto the stack. There could be a nicer solution to this problem though:

void print_leaf_paths(Node* root) {
  stack<pair<Node*, vector<Node*> > visit_stack; // has path to node as well as node
  visit_stack.push(make_pair(root, vector<Node*()));
  while (!visit_stack.empty()) {
    pair<Node*, vector<Node*> > p = visit_stack.pop();
    Node* node = p.first;
    p.second.push_back(node);
    if (node->right) visit_stack.push(make_pair(node->right, p.second));
    if (node->left) visit_stack.push(make_pair(node->left, p.second));
    if (!node->right && !node->left) {
      for (int i = 0; i < p.second.size(); i++) printf("%i ", p.second[i]->val);
      printf("\n");
    }
  }
}

Please comment if something is wrong

void printPaths(node *root){
int path[1000]={0}; //stores the paths
printallpaths(root,path,0);

}

//call print path recursively
void printallpaths( node *root, int[] path, pathlen){
if(root==NULL) return;

path[pathlen]=root->data;
pathlen++;

if(root->left==NULL && root->right==NULL) {
printpath(path,pathlen); // print path in leaf node
}else {
              printallpaths(root->left,path,pathlen);
              printallpaths(root->right,path,pathlen);
          }
 }

void printpath(int [] path, len){
int i=0;
for(i=0; i <len; i++)
printf("%d",path[i]);
printf("\n----------------------------------------------------------\n");
}

FULL WORKING CODE:
# include<stdio.h>
# include<conio.h>
# include<stdlib.h>
struct node
{
struct node*left;
struct node *right;
int info;
};
typedef struct node* NODEPTR;
int top=-1;
NODEPTR stack[50];
int stackempty()
{
if(top==-1)
return 1;
return 0;
}
int push(NODEPTR ptr)
{
if(top==49)
{
puts("stack overflow");
return 0;
}
top++;
stack[top]=ptr;
return 0;
}//end of push
NODEPTR pop()
{
NODEPTR p;
if(top==-1)
{
puts("stack empty");
return NULL;
}
else
{
p=stack[top];
top--;
return p;
}

}//end of pop function
int print_stack()
{
int i=top;
while(i>=0)
{
printf("%d ",stack[i]->info);
i--;
}
printf("\n");
}//end ofprint stack function

NODEPTR insert(int n)
{
NODEPTR temp,start,p,q;
int i;
for(i=0;i<n;i++)
{
temp=(NODEPTR)malloc(sizeof(struct node));
temp->left=NULL;
temp->right=NULL;
printf("enter item\n");
scanf("%d",&(temp->info));
if(i==0)
start=temp;
else
{
p=start;
q=start;
while(p!=NULL)
{
q=p;
if(p->info>=temp->info)
p=p->left;
else
p=p->right;
}//end of while loop
if(temp->info>q->info)
q->right=temp;
else
q->left=temp;
}//end of else
}//end of for loop
return start;
}//end of insertion in tree
int print_path(NODEPTR root)
{
NODEPTR ptr,q;
ptr=root;
while(1)
{
while(ptr->left!=NULL)
{
push(ptr);
ptr=ptr->left;
}//end of inner loop
while(ptr->right!=NULL&&ptr->left==NULL)
{
push(ptr);
ptr=ptr->right;
}//END OF LOOP
if(ptr->left==NULL)
{
printf("%d",ptr->info);
print_stack();
q=ptr;
if(stackempty())
return 0;
ptr=pop();
if(ptr->right==NULL||ptr->right==q)
{
while(ptr->right==NULL||ptr->right==q)
{
q=ptr;
if(stackempty())
return 0;
ptr=pop();
}
push(ptr);
ptr=ptr->right;

}//end of if
else
{
push(ptr);
ptr=ptr->right;
}
}//end of if loop
else
{
push(ptr);
ptr=ptr->left;
}
}//end of while loop
}//end of print_path
int main()
{
NODEPTR root;
int n;
printf("enter the number of nodes you want to enter in the tree");
scanf("%d",&n);
root=insert(n);//this is inserting as bst ..but need to insert BT
printf("inserted");
print_path(root);
printf("returned");
getch();
return 0;
}//end of main function