C++ | Optimised Approach | search 'path to C' at all nodes in the 'path to B'


#1
bool markC(TreeNode *root, int C) {
    if(not root)    return false;
    if(root->val == C)  return true;
    return markC(root->left, C) or markC(root->right, C);
}
bool traverse(TreeNode *root, int B, int C, TreeNode **ptr) {
    if(not root)        return false;
    bool foundB = (root->val == B) or \
                    traverse(root->left, B, C, ptr) or \
                    traverse(root->right, B, C, ptr);
    if(foundB and *ptr == nullptr and markC(root, C))
        *ptr = root;
    return foundB;
}
int Solution::lca(TreeNode* A, int B, int C) {
    TreeNode *ptr = nullptr;
    int res = traverse(A, B, C, &ptr);
    return ptr ? ptr->val : -1;
}