Jun 132012

Given a Binary tree and an integer, print all the ancestors of the node. For example: If the given tree is as below:

Input: 5 Output: 10 Input: 40 Output: 30 10 Input: 1 Output: 4 5 10

### Solution:

If Node of the binary tree is defined as below:

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

**Algorithm:**

To print the ancestors, the logic is as below:

- Traverse the entire tree.
- If the node is desired node, then print it and return true.
- If it is the leaf node then return false
- If it is neither the desired node nor the leaf node then call this function for left and right sub-trees.
- If anyone of them returns true, then print this node as well and return true.
- If both returns false, then return false from here also.

At any point true means the node is an ancestor of the given node. A false means that the given node is neither in the left nor in the right-sub-tree of this node, hence this node is not the ancestor.

**Code:**

bool printAncestors(Node *r, int d) { if(r == NULL) return false; if(r->data == d ) return true; if( printAncestors(root->left, d) || printAncestors(root->right, d) ) { cout << root->data << " "; return true; } else { return false; } }