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

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

DESCRIPTION:

In this article, we will be learning how to find the ancestors of a given node from a binary tree, but before that, we have to know what is a binary tree?

A binary tree is nothing but a tree in which each node can have at most two children.

So, this means that we can easily achieve our goal by using recursive approach, in which we have to go to the left and right subtree of a root and there we have to find whether the given value exists or not, if the value exists in that subtree insert all the nodes visited to reach the desired value node.

Now let's see the algorithm of the approach we just discussed.

Bool ancestor (root, value)

Step 1.

o   Case 1. Check for the current node if it is equal to the node we were searching or not. If it is, then return TRUE.

o   Case 2. And if it is NULL then return FALSE.

Step 2.

if the node is not equal to the node to be searched then call the procedure for left subtree (root->left) as well as

for the right subtree(root->right) and OR their value.

This is where the recursion calls are made.

Step 3.

o   Case 1.

- If the OR value is TRUE that means that the current node is a node by which we can reach the desired node.

- So, insert it in the ancestor_list stack.

- Return TRUE.

o   Case 2.

-  If the OR value is FALSE that means that the current node has no way to reach the desired node and it's not

an ancestor of the desired node.

- Return FALSE.

NOTE: - THIS APPROACH IS ALSO CALLED DEPTH FIRST SEARCH IN WHICH WE USED POSTORDER APPROACH.

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:- And our ancestor_list stack will be:-

50
80
40

Some results that need to be known

If the ancestor list is empty then there might be two cases

-The node to be looking for is the main root. Because it the first node to be traversed. Even though it will return TRUE (step 1 case 1) but we have to be aware that only in step 3 case 1 the nodes are added into the ancestor_list stack. But this thing makes sense also as we all know a node can't be an ancestor of its own.

Complexity

Worst case complexity will be O(n) i.e. if the tree is a single branch tree having n nodes and the node to be looking for doesn't exist.

Best case or average case complexity will be O(lg2 n) i.e. if the tree is a balanced tree or full tree.

I have also provided a more optimized code in the same git directory i.e.:-

https://github.com/pyskmr/D4datastructures/blob/master/binary%20tree/ancestor_optimised.cpp

I always put an emphasis on coding on your own but I'm still providing you the code just in case you need some help.

CODE:-

 ` 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 99100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154` `#include#include/*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 */templateclass 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 */templateclass tree:public node{ private: node *root; stack ancestor_list; public: tree(); node* getRoot(); stack getAncestorList(); void createTree(); bool ancestor(node *,C);};/* tree class default constructor.As soon as the object will be made its root will be pointed to NULL */templatetree :: tree(){ root=NULL;}/* this will return the root of the tree's object */templatenode* tree :: getRoot(){ return root;}/* this will return the ancestor list of the node we just traversed and checked */templatestack tree::getAncestorList(){ return ancestor_list;}/* this will create the tree in the example we just shown */templatevoid tree::createTree(){ root=new node(50); root->left=new node(80); root->left->left=new node(10); root->left->right=new node(40); root->left->right->left=new node(46); root->right=new node(9);}/* A recursive function to find the ancestor of a node */templatebool tree :: ancestor(node *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 obj; int value ; value=46; obj.createTree(); obj.ancestor(obj.getRoot(),value);/* a_list will store the ancestor list stack */ stack 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 "< 