The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Print all the ancestors of a given node in a Binary Tree.
In the tree shown below, ancestors of 29 are 24 ,16 and 31 .

Solution :-
As we do a recursive traversal of right and left subtrees of each node, if the given node ( X ) lies in the subtree of any
node ( P ), then P is the ancestor of the given node. See the implementation below.

#include<iostream>using namespace std;
// node structuretypedef struct tree_node {
int value;
struct tree_node *left, *right;
}node;
// recursive function to print all the ancestors of a give node
// true denotes current node is the ancestor of target node bool printAncestors(node *root, int target)
{
if (root == NULL)
return false;
if (root->value == target)
return true;
if (printAncestors(root->left,target) || printAncestors(root->right,target)) {
// if the target lies in the left subtree or the right subtree
// then it is the ancestor of the target
cout<<root->value<<" ";
return true;
}
return false;
}
// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// create the tree
node *createTree() {
node *root = getNewNode(31);
root->left = getNewNode(16);
root->right = getNewNode(52);
root->left->left = getNewNode(7);
root->left->right = getNewNode(24);
root->left->right->left = getNewNode(19);
root->left->right->right = getNewNode(29);
return root;
}
// main int main() {
node *root = NULL;
root = createTree();
printAncestors(root, 29);
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// node structuretypedef struct tree_node {
int value;
struct tree_node *left, *right;
}node;
// recursive function to print all the ancestors of a give node
// true denotes current node is the ancestor of target node bool printAncestors(node *root, int target)
{
if (root == NULL)
return false;
if (root->value == target)
return true;
if (printAncestors(root->left,target) || printAncestors(root->right,target)) {
// if the target lies in the left subtree or the right subtree
// then it is the ancestor of the target
cout<<root->value<<" ";
return true;
}
return false;
}
// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// create the tree
node *createTree() {
node *root = getNewNode(31);
root->left = getNewNode(16);
root->right = getNewNode(52);
root->left->left = getNewNode(7);
root->left->right = getNewNode(24);
root->left->right->left = getNewNode(19);
root->left->right->right = getNewNode(29);
return root;
}
// main int main() {
node *root = NULL;
root = createTree();
printAncestors(root, 29);
cout<<endl;
return 0;
}