TOPIC: C++ program to print ancestors of a given node in a binary tree.
Link to source code: https://github.com/pyskmr/D4datastructures/blob/master/binary%20tree/ancestor.cpp
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.
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
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.
Some results that need to be known
If the ancestor list is empty then there might be two cases
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
CODE:
1  #include<iostream> Note: additional header file used is stack.h for stack STL.

Comments