How can be implemented function which prints all paths of tree in C?

Question

I try to write a function which prints all the paths from the root node to the leaf nodes.

print the nodes in the order from the root to the leaf
for every node left child comes before right child
put spaces after node values, including the last one
end each path with a newline, including the last one
if the root is NULL, do not print anything

For example;

printPaths(bt1);
>2_1_
>2_3_

for this example 2 is a root, and 1-3 are leaves.

Here is my simple code, I cannot find where should be new line because when I write printf("\n") anywhere, it prints crazy outputs, so I could not find the problem in this code.

void printPaths(TreeNode* root) {

    if(root != NULL) {
        printf("%d ", root->val);
        printPaths(root->left);
        printPaths(root->right);
    }

}

Julien Lopez Julien Lopez · Accepted Answer · 2016-05-27T13:07:02

You need a newline at the "end of each path", so when you reach a leaf:

if (root->left == NULL && root->right == NULL)
    printf("\n");

However, you will not be able to print the entire path again with your code, you need to keep track of your path as you visit the tree and print the path when you reach a leaf:

void printPaths(TreeNode* root, int path[], int len)
{
  if (root == NULL) // if the root is NULL, do not print anything
    return;

  path[len++] = root->val; // add root to your path

  if (root->left == NULL && root->right == NULL) // we reached a leaf
    printPath(path, len); // print the path we followed to reach this leaf
  else
  {
    printPaths(root->left, path, len);
    printPaths(root->right, path, len);
  }
}

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

How can be implemented function which prints all paths of tree in C?

1 Answers