LCA(LeastCommon Ancestor)
Most of you guys might have seen the problem about finding the LCA(LeastCommon Ancestor) for the 2 nodes given in a tree.
Note : Here I am taking ancestor as 'Ancestor' only & as per me no node can be its own ancestor, no matter what theory is given for this.
So below I present one solution to find the correct LCA, plus it is applicable for any number of nodes for which one
wants to find the LCA. Also if any one of the given nodes is not present in the tree, then it will give the message that all
the given nodes are not present, else will give the correct LCA.
Please try once & let me know about your thoughts on this.
You can refer below tree to test the below code or you can create your own using the code given below.
Note : Here I am taking ancestor as 'Ancestor' only & as per me no node can be its own ancestor, no matter what theory is given for this.
So below I present one solution to find the correct LCA, plus it is applicable for any number of nodes for which one
wants to find the LCA. Also if any one of the given nodes is not present in the tree, then it will give the message that all
the given nodes are not present, else will give the correct LCA.
Please try once & let me know about your thoughts on this.
You can refer below tree to test the below code or you can create your own using the code given below.
Now integrate the below code with the above to execute & test the code against the tree given above. Change the test values as per the requirements.
So above I have used 2 versions of LCA(). LCA1() is the implementation of the idea like shown across internet to find the common Ancestor & LCA() is the implementation of my understanding of the word 'Ancestor'. So check the capabilities of both the methods. Using my method (1) you will be giving the correct 'Ancestor' (2) It will check if both the nodes present then only a valid 'Ancestor' can exist. (3) This method can be used to find the 'Ancestor' of multiple nodes.
Assumption :- All nodes in the given tree must be unique.
Assumption :- All nodes in the given tree must be unique.
Below is the implementation which you see across the internet which is wrong as per my understanding of the word 'Ancestor'. It is also wrong in the sense that if one node is not present then it will return the present node as the answer. Plus it has unsaid assumption that both the nodes must be present in the tree.
Try both the above methods & check the difference. Please let me know if you see any issue.
But I still wonder about how such wrong understanding is being used in multiple interviews of even big companies to select the candidates where the interviewers themselves don't understand the basic concepts.
But I still wonder about how such wrong understanding is being used in multiple interviews of even big companies to select the candidates where the interviewers themselves don't understand the basic concepts.
