Finding the least common ancestor of two nodes in a tree
I was given this question in an interview and was unable to answer it, although I know how to solve the problem. The reason I didn't know what to do is because I was asked this question:
class Node{
int val;
Node *left, *right;
};
int LCA(int a, int b){
//your code here
}
The interviewer wanted me to find the least common ancestor of a and b. I asked if we had a pointer to the root of the tree we were browsing and he said no. So I was at a loss as to how I should solve the problem, given that I don't even have a tree to work with.
Is it possible to find in this case the least common ancestor? Should I assume we were given a global Node*
which was the root of a tree or something? Has anyone experienced a similar problem?
source to share
No, It is Immpossible. To answer the question you asked, you need to find the path between node and its ancestors. To do this, you need either a node as a starting point or a parent reference in each node. Or an ancestor (or an ancestor of an ancestor) as a starting point and reference to children in each node.
source to share
From the way you described the interaction with the interview, I suspect this was a controversial issue. This is probably a weak attempt to see how persistent you are with your clarification questions.
If I were, after getting feedback that there is no root, I would ask if there is another way to have node values related to each other. If the nodes have a mathematical relationship, you may not need the root node to solve the LCA problem.
Another tactic is to determine how to insert, remove, and find nodes. That is, find out which APIs are available. You may have discovered that the interviewer provided a parent API.
Sometimes an interview is like an Adventure game, and the interviewer really wants you to find your way out of the winding maze (however unfair it may be).
source to share