# Program to Print Ancestors of a Node in Binary Tree

• 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 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
```