CareerCup

My algo is .
all three pairs A & B , B & C , C & A has same LCA.

Approach:

Traverse the tree:

a) if C value is found return True and keep searching for B
b) When B is found in the path mark as True and keep searching for A along the same path
c) When A is also found return True and exit
d) If any of A or B or root or leaf is encountered while the other elements are not found return False. e.g if A is found when B is not still found

b_found = False

def checkpath(root):
  
  global b_found

  if not root:
    return False

  if root.val == C:
    return True

  m = checkpath(root.left) or checkpath(root.right)
  
  if m :
    if root.val == B:
      b_found = True
    elif root.val == A:
      if not b_found:
        return False
    return True
  else:
    return False

b_found = False

def checkpath(root):
  
  global b_found

  if not root:
    return False

  if root.val == C:
    return True

  m = checkpath(root.left) or checkpath(root.right)
  
  if m :
    if root.val == B:
      b_found = True
    elif root.val == A:
      if not b_found:
        return False
    return True
  else:
    return False

b_found = False

def checkpath(root):
  
  global b_found

  if not root:
    return False

  if root.val == C:
    return True

  m = checkpath(root.left) or checkpath(root.right)
  
  if m :
    if root.val == B:
      b_found = True
    elif root.val == A:
      if not b_found:
        return False
    return True
  else:
    return False

Is the foll good enough or am I missing something.Call would be Find(head,A)

Find(Node n,Node req){
   if(n==null)
      return false;
   if(req==A)
      if(n==A)
         return Find(n,B);
   if(req==B)
      if(n==B)
         return Find(n,C);
   if(req==C)
      if(n==C)
         return true;
   else
      return Find(n.left,req)||Find(n.right,req);
}

bool find(node *start, node *dest){
    if(!start){
       return false;
    }
    
    if(start == dest){
       return true;
    }
   
    return find(start->left, dest) || find(start->right, dest);
}

bool Func(node *A, node *B, node *C){
   return (find(A, B)&&find(B, C));
}

Do depth first of Binary tree and note arrival and departure time of Node .
arrival time / departure time

1 / 10
a
/ \
2/7 b c 8/9
/ \
3/4 d e 5/6


following property will hold

arrival time (A) < arrival time (B) < arrival time (C)

dep time (A) > dep time (B) > dep time (C)

//found flag 0
//found flag 1

//calling conv
Func(t,-1,a,b,c)

bool Func(tree *t,int flag,tree *a,tree *b,tree *c)
{
if(!t && flag !=1) return false;
else if(t->val == a->val)
flag=0;
else if(t->val == b->val && flag==0)
flag=1;
else if(t->val == c->val && flag==1)
return true;
else
return(Func(t->left,flag) || Func(t->right,flag))


}

template <typename T>
bool checkPath(BTNode<T> *t, int lookfor, T a, T b, T c) {
  if (t!=NULL) {
    T d = t->data;
    if (lookfor == 0) {
      int newlook = d == a ? lookfor+1:lookfor;
      if (checkPath(t->left, newlook, a, b, c)) return true;
      return checkPath(t->right, newlook, a, b, c);
    }
    else if (lookfor == 1) {
      int newlook = d == b ? lookfor+1:lookfor;
      if (checkPath(t->left, newlook, a, b, c)) return true;
      return checkPath(t->right, newlook, a, b, c);
    }
    else {
      if (d == c) return true;
      if (checkPath(t->left, lookfor, a, b, c)) return true;
      return checkPath(t->right, lookfor, a, b, c);
    }
  }
  return false;
}

public bool FindPath(int[] path)
{
return FindRecursive(_head, path, 0);
}

bool FindRecursive(TreeNode current, int[] path, int currentIndex)
{
if (current != null)
{
if (current.Value == path[currentIndex])
{
if (currentIndex == path.Length - 1)
{
return true;
}
currentIndex++;
}
return FindRecursive(current.Left, path, currentIndex) || FindRecursive(current.Right, path, currentIndex);
}
return false;
}

I am probably wrong but does the following approach work
1) Find the "Lowest Common Ancestor" of A and C
2) Modify this algorithm to keep track whether B is encountered on the path selected.