Algorithm:
initialize: pathlen = 0, path[1000]
/*1000 is some max limit for paths, it can change*/
/*printPathsRecur traverses nodes of tree in preorder */
printPathsRecur(tree, path[], pathlen)
1) If node is not NULL then
a) push data to path array:
path[pathlen] = node->data.
b) increment pathlen
pathlen++
2) If node is a leaf node then print the path array.
3) Else
a) Call printPathsRecur for left subtree
printPathsRecur(node->left, path, pathLen)
b) Call printPathsRecur for right subtree.
printPathsRecur(node->right, path, pathLen)
void printArray(int [], int);
void printPathsRecur(struct node*, int [], int);
struct node* newNode(int );
void printPaths(struct node*);
/* Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(struct node* node)
{
int path[1000];
printPathsRecur(node, path, 0);
}
void printPathsRecur(struct node* node, int path[], int pathLen)
{
if (node==NULL) return;
/* append this node to the path array */
path[pathLen] = node->data;
pathLen++;
/* it's a leaf, so print the path that led to here */
if (node->left==NULL && node->right==NULL)
{
printArray(path, pathLen);
}
else
{
/* otherwise try both subtrees */
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
/* Utility that prints out an array on a line */
void printArray(int ints[], int len)
{
int i;
for (i=0; i<len; i++) {
printf("%d ", ints[i]);
}
printf("\n");
}
