fork 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);
  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)
  20.     {
  21.     int path[1000];
  22.     printPathsRecur(node, path, 0);
  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)
  29.     {
  30.     if(node==NULL)
  31.     return;
  32.     path[pathlen] = node->data;
  33.     pathlen++;
  34.     if(node->left==NULL && node->right==NULL)
  35.     {
  36.     printArray(path,pathlen);
  37.     }
  38.     else{
  39.     printPathsRecur(node->left,path,pathlen);
  40.     printPathsRecur(node->right,path,pathlen);
  41.     }
  42.     }
  43.  
  44.     /* UTILITY FUNCTIONS */
  45.     /* Utility that prints out an array on a line. */
  46.     void printArray(int ints[], int len)
  47.     {
  48.     int i;
  49.     for (i=0; i<len; i++)
  50.     {
  51.     printf("%d ", ints[i]);
  52.     }
  53.     printf("\n");
  54.     }
  55.  
  56.     /* utility that allocates a new node with the
  57.       given data and NULL left and right pointers. */
  58.     struct node* newnode(int data)
  59.     {
  60.     struct node* node = (struct node*)
  61.     malloc(sizeof(struct node));
  62.     node->data = data;
  63.     node->left = NULL;
  64.     node->right = NULL;
  65.  
  66.     return(node);
  67.     }
  68.  
  69.     /* Driver program to test above functions*/
  70.     int main()
  71.     {
  72.  
  73.     /* Constructed binary tree is
  74.       10
  75.       / \
  76.       8 2
  77.       / \ /
  78.       3 5 2
  79.       */
  80.     struct node *root = newnode(10);
  81.     root->left = newnode(8);
  82.     root->right = newnode(2);
  83.     root->left->left = newnode(3);
  84.     root->left->right = newnode(5);
  85.     root->right->left = newnode(2);
  86.  
  87.     printPaths(root);
  88.  
  89.     getchar();
  90.     return 0;
  91.     }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 8 3 
10 8 5 
10 2 2
https://ideone.com/5YOl3v
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!