Print all Root to Leaf paths of a Binary Tree

Write a C program to print all root node to leaf node path of a given binary tree.

Given a binary tree, we have to print all root to leaf node path for given binary tree. We will traverse every node of binary tree using pre order traversal and keep track of the nodes in our current path using a path array. Whenever we reach a leaf node, we will print the content of path array. Node at index 0 is the root node, and at index 1 id the node of level 1 in our current path and so on.

Algorithm to print all root to leaf paths of a binary tree

We will use and array(let's say pathArray) to keep track of out path till now while doing pre order traversal. A node in our path at level X will be stored at index X.
Let "node" be the pointer to a node at level L while doing pre order traversal.
Store the value of node in pathArray at index L.
Check if node is a leaf node. If yes, then print path Array else continue pre order traversal of left and right sub tree at level L+1.

Time Complexity : O(n), we are just doing pre order traversal with an additional array as function argument.

C program print all root to leaf path of a binary tree

#include <stdio.h>
#include <limits.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         9    12
        / \    \
       4  50    -7
      / \
     18  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
     
    root->left = getNewNode(9);
    root->right = getNewNode(12);
     
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(50);
    root->right->right = getNewNode(-7);
     
    root->left->left->left = getNewNode(18);
    root->left->left->right = getNewNode(9);
    
    return root;
}

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

/*
 Prints all root to leaf path   
 */
void printRootToLeafPath(struct node *nodeptr, int *path, int index){
    if(nodeptr != NULL){
        /* Add current node in path  */
        path[index] = nodeptr->data;
        /* Leaf Node: print path */
        if(nodeptr->left == NULL && nodeptr->right == NULL)
            printPath(path, index);
        /* Recursively traverse left sub-tree */
        printRootToLeafPath(nodeptr->left, path, index+1);
        /* Recursively traverse right sub-tree */
        printRootToLeafPath(nodeptr->right, path, index+1);
    }
}

int main() {
    struct node *root = generateBTree(); 
 int path[100];   
    
    printRootToLeafPath(root, &path, 0);
    
    getchar();
    return 0; 
}

Output