- Write a C program to check if there exist a path from root to leaf whose sum is N.

Given a binary tree and a node N, we have to **print all ancestor nodes of N** in given binary tree. In other words, we have to print all the nodes in a path from root node to node N. Here we are going to use a recursive approach to **print ancestors of a node**.

**Algorithm to print all ancestors of a node in binary tree**

Let "root" be the pointer to the root node of given binary tree.

- if root is equal to NULL, return false(node not found).
- If root is equal to N, return true(node found).
- Recursively search N in left and right sub tree. If any one the sub tree contains N, then root must be an ancestor of N.
- If neither left sub tree nor right sub tree contains N, then N is not ancestor of N.

**Time Complexity**: O(n), we are traversing given binary tree only once.

## C program to print all ancestors of a node in binary tree

#include <stdio.h> #define TRUE 1 #define FALSE 0 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 / \ 2 3 / \ / \ 4 5 6 7 / \ \ 8 9 10 */ struct node* generateBTree(){ // Root Node struct node* root = getNewNode(1); // Level 2 nodes root->left = getNewNode(2); root->right = getNewNode(3); // Level 3 nodes root->left->left = getNewNode(4); root->left->right = getNewNode(5); root->right->left = getNewNode(6); root->right->right = getNewNode(7); // Level 4 nodes root->left->left->left = getNewNode(8); root->left->left->right = getNewNode(9); root->right->right->right = getNewNode(10); return root; } /* Prints all Ancestors of a node(num) */ int printAncestorsOfNode(struct node* root, int num) { /* Recursion termination condition */ if (root == NULL) return FALSE; if (root->data == num) return TRUE; if (printAncestorsOfNode(root->left, num) || printAncestorsOfNode(root->right, num) ) { /* If num is present is any any of the two sub tree of root, then root is an ancestor of num */ printf("%d ", root->data); return TRUE; } else { /* If none of the sub tree of root contains num, then root is not an ancestor of num */ return FALSE; } } int main() { struct node *root = generateBTree(); /* Printing ancestor's of nodes */ printf("Ancestors of 9\n"); printAncestorsOfNode(root, 9); printf("\nAncestors of 6\n"); printAncestorsOfNode(root, 6); getchar(); return 0; }Output

Ancestors of 9 4 2 1 Ancestors of 6 3 1