So tried to find out how this recursion works ??
don't worry , I got you covered
See the approach is simple it can even help you fetch 4 or 5 or 6 .. k no of lca
what u need to do is maintain a variable count
if you found a solution node (any node out of 3) just return previous + 1 from that side (yeah u got it right , we are maintaing sum , and if the node doesnt matches then go to its left then right try to find the node and return the prev + 1)
if this prev+1 returns 3 then boom your ans is right in front of you thats the node u wanted to cater , return that node via a global variable
heres the code:
/**********************************************************
Following is the Binary Tree Node class structure.
template <typename T>
class BinaryTreeNode {
public :
T data;
BinaryTreeNode<T> *left;
BinaryTreeNode<T> *right;
BinaryTreeNode(T data) {
this -> data = data;
left = NULL;
right = NULL;
}
};
***********************************************************/
BinaryTreeNode<int>* ret = nullptr;
int countMatches(BinaryTreeNode<int>* root, int node1, int node2, int node3) {
if (root == nullptr) {
return 0;
}
int count = (root->data == node1) + (root->data == node2) + (root->data == node3);
int leftCount = countMatches(root->left, node1, node2, node3);
int rightCount = countMatches(root->right, node1, node2, node3);
int total = count + leftCount + rightCount;
if (total == 3 && ret == nullptr) {
ret = root;
}
return total;
}
BinaryTreeNode<int>* lcaOfThreeNodes(BinaryTreeNode<int>* root, int node1, int node2, int node3) {
ret = nullptr;
countMatches(root, node1, node2, node3);
return ret;
}