fork(3) download
copy 
  1.     #include<stdio.h>
  2.     #include<stdlib.h>
  3.  
  4.     /* A binary tree node has data, pointer to left child
  5.       and a pointer to right child */
  6.     struct node
  7.     {
  8.     int data;
  9.     struct node* left;
  10.     struct node* right;
  11.     };
  12.  
  13.     /* Prototypes for funtions needed in printPaths() */
  14.     void printPathsRecur(struct node* node, int path[], int pathLen,int sum);
  15.     void printArray(int ints[], int len);
  16.  
  17.     /*Given a binary tree, print out all of its root-to-leaf
  18.      paths, one per line. Uses a recursive helper to do the work.*/
  19.     void printPaths(struct node* node,int sum)
  20.     {
  21.     int path[1000];
  22.     printPathsRecur(node, path, 0, sum);
  23.     }
  24.  
  25.     /* Recursive helper function -- given a node, and an array containing
  26.      the path from the root node up to but not including this node,
  27.      print out all the root-leaf paths.*/
  28.     void printPathsRecur(struct node* node, int path[], int pathlen,int sum)
  29.     {
  30.     if(node==NULL)
  31.     return;
  32.     path[pathlen] = node->data;
  33.     sum-=node->data;
  34.     pathlen++;
  35.     if(node->left==NULL && node->right==NULL && sum==0)
  36.     {
  37.     printArray(path,pathlen);
  38.     }
  39.     else
  40.     {
  41.     printPathsRecur(node->left,path,pathlen,sum);
  42.     printPathsRecur(node->right,path,pathlen,sum);
  43.     }
  44.     }
  45.  
  46.     /* UTILITY FUNCTIONS */
  47.     /* Utility that prints out an array on a line. */
  48.     void printArray(int ints[], int len)
  49.     {
  50.     int i;
  51.     for (i=0; i<len; i++)
  52.     {
  53.     printf("%d ", ints[i]);
  54.     }
  55.     printf("\n");
  56.     }
  57.  
  58.     /* utility that allocates a new node with the
  59.       given data and NULL left and right pointers. */
  60.     struct node* newnode(int data)
  61.     {
  62.     struct node* node = (struct node*)
  63.     malloc(sizeof(struct node));
  64.     node->data = data;
  65.     node->left = NULL;
  66.     node->right = NULL;
  67.  
  68.     return(node);
  69.     }
  70.  
  71.     /* Driver program to test above functions*/
  72.     int main()
  73.     {
  74.  
  75.     /* Constructed binary tree is
  76.       10
  77.       / \
  78.       8 2
  79.       / \ /
  80.       3 5 2
  81.       */
  82.     struct node *root = newnode(10);
  83.     root->left = newnode(8);
  84.     root->right = newnode(2);
  85.     root->left->left = newnode(3);
  86.     root->left->right = newnode(5);
  87.     root->right->left = newnode(2);
  88.     int sum = 14; 
  89.     printPaths(root,sum);
  90.  
  91.     getchar();
  92.     return 0;
  93.     }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 2 2
https://ideone.com/zF7o6n
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!