- 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

1 9 4 18 1 9 4 9 1 9 50 1 12 -7