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