Let's take an example to make things clearer and more understandable.

Consider this as our tree and we want to search the ancestor of node 46.

Initially, the current root node would be 50

Step 1. So, from step 1we found out it is neither the desired node and nor a NULL node. So, it means that we have to go to the next step that is step 2.

Step 2. Now we are doing recursive calls to the left of the root and right of the root and checking their boolean values. Therefore, our call stack will be.

Step 3. This will be pending in the call stack.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

Now since the left subtree was called first therefore 80 would be the current root value.

Step 1. Again, nothing in step 1.

Step 2. A recursive call to the left and right subtree of the current root. Therefore, our call stack would be.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

Now since the left subtree was called first therefore 10 would be the current root value.

Step 1. Again, nothing in step 1.

Step 2. A recursive call to the left and right subtree of the current root. Therefore our call stack would be the following figure. 

But since 10 has no child so its right and left child would be NULL.

And after the call to them, they will return FALSE (because of the "step 1 case 2" in their call).

Since we got FALSE from both children of 10, therefore, the OR of them will be also FALSE(because FALSE OR FALSE is FALSE)
which means (10,46) will return FALSE(step 3 case 2)

But we have the right subtree still needs to be called that is (40,46)

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

Therefore the root would be 40.

Step 1. Again, nothing in step 1.

Step 2. A recursive call to the left and right subtree of the current root. Therefore, our call stack would be the following figure.

But when we do so we will find that the left child of 40 is 46 and the value that needed to be checked out was also 46, which means it will return TRUE(Step 1 case 1 in the left child call of 40).  

Whereas the right child of 40 will return FALSE(because of the step 1 case 2 in their call).

Since we got one TRUE and one FALSE from both children of 40, therefore, the OR of them will be also TRUE(because TRUE OR FALSE is TRUE) which means (40,46) will be TRUE(step 3 case 1)

So, add 40 to the ancestor_list stack

And return TRUE.

Now since it was the recursive call and we returned something, therefore the previous call will start its execution in which we were at step 2 and we got two values from10 (FALSE) and 40 (TRUE) respectively.so if we OR the returned value we will
get a TRUE.

therefore step 3 case 1 will be satisfied.

So, add 80 to the ancestor_list stack

And return TRUE.

We will return to the calling stack (back to the recursive calling function) where we were at step 2, where we processed the left child of the main root i.e. 50.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

Now we will call a recursive call to the right child of 50 i.e. (9,46).

Since the right subtree was called first therefore 9 would be the current root value.

Step 1. Again, nothing in step 1.

Step 2. A recursive call to the left and right subtree of the current root. Therefore, our call stack would be the following figure. But since 9 has no child so it's right and left child
would be NULL.

And after the call to them, they will return FALSE (because of the step 1 case 2 in their call).

Since we got FALSE from both children of 9, therefore, the OR of them will be also FALSE(because FALSE OR FALSE is FALSE)
which means (9,46) will return FALSE(step 3 case 2).

Now since it was the recursive call and we returned something, therefore the previous call will start its execution in which we were at step 2 and we got two values from80 (TRUE) and 9 (FALSE) respectively.so if we OR the returned value we will
get a TRUE.

So, add 50 to theancestor_list stack

And return TRUE.

And 50 was the first recursive call so we don't have anything else to work on and the control would go back to the main.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

Our traversal would look like:-

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

#include<iostream>
#include<stack>

/*

C++ program to print ancestors of a given node in binary tree.

*/

using namespace std;

/* a base class is created which contain the data of every node in the tree */

template<class P>
class node
{
	public:
		P data;
		node *left,*right;
		node()
		{
			left=NULL;
			right= NULL;
		}
		node(P value)
		{
			data = value;
			left=right=NULL;
		}
};

/* class tree inheriting node class and having a root object of the node as its class member */

template<class C>
class tree:public node<C>
{
	private:
		node<C> *root;
		stack<C> ancestor_list;
	public:
		tree();
		node<C>* getRoot();
		stack<C> getAncestorList();
		void createTree();
		bool ancestor(node<C> *,C);
};

/* tree class default constructor.As soon as the object will be made its root will be pointed to NULL */

template<class C>
tree<C> :: tree()
{
	root=NULL;
}

/* this will return the root of the tree's object */

template<class C>
node<C>* tree<C> :: getRoot()
{
	return root;
}

/* this will return the ancestor list of the node we just traversed and checked */

template<class C>
stack<C> tree<C>::getAncestorList()
{
	return ancestor_list;
}

/* this will create the tree in the example we just shown */
template<class C>
void tree<C>::createTree()
{
	root=new node<C>(50);
	
	root->left=new node<C>(80);
	root->left->left=new node<C>(10);
	root->left->right=new node<C>(40);
	root->left->right->left=new node<C>(46);

	root->right=new node<C>(9);
}

/* A recursive function to find the ancestor of a node */
template<class C>
bool tree<C> :: ancestor(node<C> *r,C value)
{

/* check if the current root is NULL or not*/	
	
	if(r==NULL)
	{
		return false;
	}

/* this will check if the current node is value or not */
	
	else if(r->data == value)
	{
		return true;
	}

/* recursive section where we OR the bool value from the left and right subtree of the root */ 
	
	else if(ancestor(r->left,value) | ancestor(r->right,value) )
	{
		ancestor_list.push(r->data);
		return true;
	}

/* if nothing found or the above condition is also false */

	else 
	{
		return false;
	}
}

int main()
{
	tree<int> obj;
	int value ;
	value=46;
	
	obj.createTree();
	obj.ancestor(obj.getRoot(),value);

/* a_list will store the ancestor list stack */

	stack<int> a_list = obj.getAncestorList();

/* if there is no ancestor then there might a case of no node found or the root being the node that was the node to be searched upon */
	
	if(a_list.size()==0)
	{
		cout<<"no ancestor found\n";
	}

/* if there are ancesotor just show them */

	else
	{
		cout<<"\nancestors of "<<value<<" are following\n";
		while(a_list.size()!=0)
		{
			cout<< a_list.top()<<"\n";
			a_list.pop();
		}
	}

	return 0;
}

Note:- additional header file used is stack.h for stack STL.

OUTPUT :-












KEEP UP THE GOOD WORK AND KEEP CODING. (: